To start with, I think jZed has some good suggestions, structure is helpful. And Roy is right too, you are only limited to the character set you choose. He gives an example of 0-9a-z, but there are even more characters than that in the ASCII set (not counting the unprintable ones of course).

the brevity constraint is simply to handle situations that seem to come up a lot ... (for example, the "configuration name" has to appear on a cell phone screen, or on the readout of a portable mp3 player)

Hmmm, this is an issue. At that point I would consider different outputs for different devices. We did some experimentation in the early days of WAP at the Ad agency I worked for. We did an example site-let with one HTML (browser on a PC) interface, and one WAP (for those early Nokia's) interface. The copy-writers wanted to put a lot of information on the screens, and we (and the usability guy) had to explain to them that it just wouldn't work for both, and would make the WAP version virtually unusable. We eventaully convinced them to re-write the copy for the WAP version and forgo some of the more flowery wording. Not everything can be like Java (write once, run everywhere) (yes, that is heavy in sarcasm :)

What would the 'compact' format look like?

Well, i assume your items need to be unique. In that case I would put some kind of unique ID, maybe some MD5 digest based off of some "random" input. This gives you your uniqueness. After that, its kind of like a bit-string, but you use Roy's idea of 0-9a-z as your "bit"s.

Perhaps the constraints are mutually incompatible, but perhaps they're not.

That's business logic, you should not put that in your data.