Yup, the scientific and artistic merits of higher sample rates is a long area of debate.

You are right that Nyquist comes into play which says that for a given sample frequency you can perfectly reconstruct digital signals with frequencies up to half Nyquist.

However, I think you are a little confused after this point when you say the "highest possible recorded frequency" is around 20-22kHz.
What is actually true is that most people can't HEAR above 20kHz or so and so people argue that you don't need to record above those frequencies. In fact some people can hear well over 20kHz and so this is an average limitation. There are several factors that make recording at higher sample rates of interest.

For one, all digital recording systems have to worry about aliasing and therefore the audio needs to be filtered to "kill" all frequencies above Nyquist. If your sample rate is low enough to be near the 20kHz hearing limit, then these filters have to be "brick walls" and work very hard. This can cause audible artifacts in frequencies that you can hear. The higher the sample rate, the less hard the filters may have to work.

There are also lots of non-linearities in our ears and hearing system. In fact frequencies higher than 20kHz can interact and create audible audio at lower frequencies. Bizaare but true and some people think this might have something to do with why people like higher sample rates.

There's also the issue that not everything we experience with audio is actually "heard". We also perceive audio by bone conduction (bass) and through our skin and this may be part of it too.

It's a wide area of debate and can verge on a "religious debate". Given that, I suggest you record at whatever your hardware can handle and what you can appreciate.

Regarding MP3, I think you're confusing sample rate with data rate. MP3 at 128k is actually stereo audio being encoded at 128 kilo bits per second. This is usually encoding of 44.1 kHz sampled audio. MP3 is a lossy data reduction scheme that uses psychoacoustics to dramatically reduced data rate (i.e. getting about 10 to one compression of PCM audio by throwing away portions of the audio you don't hear based on frequency masking).

When you encode MP3 below 128kbps, one way to reduce the bit rate requirements is to reduce the bandwidth of the audio (MP3 is actually limited to about 16kHz I think). As the rate goes down, so does the bandwidth as the data rate is essentially tied to how many frequency bins you're trying to encode (this is a gross simplification but helps some).

I've worked a lot on the Dolby Digital and Dolby E audio coding systems here in San Francisco, so have spent some time in this area :)

Since I've covered several topics which normally are dealt with over months of classes there ARE A LOT of things I've glossed over + I'm tired (and I'm sure others will point out) but it's enough to get some good Google sessions going :)

Have fun!
bgc