I've taken to listening to MP3's at work using headphones. I've got a nice pair of cans that seem to give good sound clarity, but I'm increasingly dissappointed with MP3's while listening through them. Case in point at the moment is Toploader's "Dancing in the Moonlight", great track but the clapping that goes through the track is horribly distorted. The other one was King Crimson's amazing "Lark's Tongues in Aspic", which has some incredibly intense sections with cymbals and triangles, and it just sounds like a distorted mess through these cans. Actually as an aside, the vinyl version of Larks Tongues in Aspic actually has significantly more clarity and depth than the CD version. I guess you really do lose something even in 16bit audio.
I didn't encode these, so I don't know what was used (some pointy clicky Win32 thingy), it's just the work jukebox, but I guess headphones make a big difference to how picky you get with your music - I never noticed this stuff over regular speakers, and for the majority of music it doesn't matter, but I'm certainly starting to see why some people complain about MP3's. Maybe I should just unplug the headphones and blare out the music for everyone, though finding King Crimson fans isn't an easy task