The biggest problem with MP3s in the beginning was the imperfect psychoacoustic modeling. While it may not be computationally possible to build a perfect model of human hearing, things have improved dramatically since those early days. So yeah, MP3s (and other lossy encoding schemes) throw away four-fifths (or more) of the data, but it's stuff your brain can't pick out anyway.
The other part of the encoding, storing the data as cosine coeffecients rather than linear amplitude really isn't that lossy at at all. Considering the reconstruction filter basically plots sinusoidal waveforms between the samples. Plus the signal is band limited to the human hearing range, so there's an upper limit on how accurate the cosine transform has to be.
I still prefer to acquire music in PCM format, but that's just because there are real issues with multi-generational recompressions, and when a better system for compressing audio to take it with me comes along I like to be able to go back to a complete data set for a fresh export.
