Download spek. Open audio file. If there is a visible line lower than 16kHz, it's most likely a bad encode and you should get new audio.
Audio is a touchy subject for some people and is difficult to diagnose/prove. With the vast number of codecs out there and the problems inherent with lossy audio, it can be difficult to ensure that your high quality audio is actually high quality.
Osu! fully supports mpeg I layer 3 audio (commonly known as mp3) and partially supports Vorbis (commonly known as ogg vorbis). Vorbis is superior to mp3 in every way except one: application support. It is released under GPL but few audio and media players support Vorbis for various reasons that I won't go into here. It is currently bad practice to use Vorbis in Osu! so please make sure you use mp3. AAC (commonly known as m4a) is another proprietary format that is commonly used in audio/video streaming services and is equivalent to/slightly better than Vorbis in terms of sound quality after minimal encodings. Unfortunately AAC isn't supported by Osu! and is tied up with software patents. Thanks Apple/Nokia/Bell/Youtube/etc...
A common problem now is the re-encoding of low bitrates into higher bitrates. If you take audio, encode it with 96 kbps AAC (common on youtube) then re-encode into 192 kbps MP3, you haven't improved the quality of the audio, you have actually degraded it. To anyone with bad ears or no reference, it may sound fine, but to those who do care, it can be very poor. In the past, maps have been ranked with poor encoding like this, and hopefully this guide will prevent poor audio from being qualified and ranked.
If you are not blessed with good ears, it is still possible to determine the quality of audio by visually looking at the spectrogram. Personally I use spek, but audacity and other professional tools exist to visualize this data.
Spek - an audio spectrogram generator (download)
The Dark Side of Phobos - a Doom Remix project with lossless audio (download)
FFmpeg - a popular LGPL audio/video transcoding tool (download)
Hearing Test - website which will play high frequency audio (link)
100 Re-encodes - website which has examples of re-encoded audio 100 times to enhance the distortions generated by encoding (link)
How to check quality of MP3 - article similar to this one (link)
Image Gallery - use this to compare spectrograms on imgur rather than in this thread. Note the AAC images were likely poorly encoded, but I threw them in there for comparison.
Files Generated - Download the files and take a listen if you're so inclined.
Part 1: Lossless is not always lossless!
Amateurs will sometimes create music using lossy methods, then release them as "lossless". Unfortunately, if you do this you lose a lot of data especially in the 16kHz+ range (human hearing ranges from 2kHz to 20kHz on average and that range usually decreases with age). You can end up with very poor quality spectrograms:
This song was created mostly with lossy audio and the lossless encode shows this. It's not a terrible thing in most cases, but there is a distinct visible line at around 16kHz on both, which shows that the audio is clearly being cut off at frequencies above 16kHz. Most people can't hear it very well, but it has an effect of being very "tinny", like you have a bucket over your head.
If we take a look at a song recorded with nice sound effects and vocals that were recorded rather than computer generated, you'll see that much of the inaudible spectrum remains intact in the lossless version, but the lossy version cuts most of it out:
Part 2: Frequency cut offs
Since humans really have a hard time hearing above 12 kHz especially when it's covered up by more audible sounds, there is some science to just chopping off everything above 16kHz in audio to compress the audio more. You can test your hearing here: Hearing Test up to 22kHz. For reference, on my sound setup I can barely hear 17kHz, and everything above that sounds silent. I am not an audiophile. MP3 is fairly aggressive at using frequency cutoffs and will almost always cutoff most sound above 16kHz. High Quality MP3 may cutoff at 20kHz. Low Quality MP3 will cut off at 15kHz or lower.
Part 3: Clipping
Clipping happens when the waveform is too loud for the container. Usually "mastered" files are perfect and don't have any clipping causing distortion. However, the lossy audio codec can sometime make sections louder than what they are supposed to be, causing a distinct clip that doesn't look like it fits in the spectrum. For more information, read up on How to check quality of MP3. I created this by increasing the volume and allowing clipping:
Clipping is a bit of a mixed bag, as it can cause distortion, but that distortion can usually be minimized by reducing the volume on the audio using something like MP3Gain or Audacity.
Audio quality isn't easy to determine. While changing the ranking criteria to include mentioning a 16kHz minimum cutoff could work, it's not feasible and should be taken on a case by case basis. Exemptions should be made when someone takes a close look at it and deems that the quality is not affected negatively, or marathon maps that need to reduce bitrate as much as possible to fit within filesize limits. However, 99% of the time, if the frequency cutoff of the spectrogram is under 16kHz, the audio is of poor quality and a new file should be obtained.