That is why some normalization software tries to work on the "power" of the sounds instead of their amplitude like most of them do.
At that point we're getting into different definitions of normalization.
The official definition is to increase the volume of the waveform until its maximum peak is just short of clipping (regardless of the frequency). In that statement, you're referring to a different thing.
Regarding the percentage of CDs that weren't normalized, I was basing my "percentage" on my meager collection of about 200 major-label CDs. Everyone's collection is going to have a different percentage. I, too, have noticed that things like folk music sampler CDs (and other CDs that don't have an extremely large press run) tend to be more likely to be not normalized.
My main point is that even when two differently-produced pieces of music are equally normalized, they will still sound like they are playing at radically different volumes. Normalization won't make all your songs sound like they are at the same volume if they are produced differently.