Before I go any further, it's worth pointing out that if the above findings differ from your own experiences, this may be 1) because you have different (more sensitive, less sensitive) hearing, or you've been encoding your files using different settings to the ones I've used.
MP3 encoding, in particular, is sensitive to the abuse of settings, and there's plenty of software out there that uses inoptimal settings. If you're that way inclined, try using the LAME MP3 command line encoder and play around with the various settings. You'll soon see what I mean.
So, for my tests I've tried to use the best, or recommended settings for LAME MP3 (version 3.97) in order to give it a fair chance of performing well against the others. In the case of AAC I used iTunes to perform the rips; with WMA I used Windows Media Player 11; and for Ogg Vorbis, I used the excellent Foobar 2000 music player.