Over Compressed Recordings: Does Pitch Reduction Make Them Sound Better?

No. Automatic from the daw . But you have to use the right algorythm for the source ( no rythm dedicated one on voice for example).

Once done it with a (virtuoso) pianist in front of me. Time stretched the take a lot ( like 5%), she didn't noticed the track played faster until the 5th or 6th playback when she asked a rerecording/overdub.

People are people, and if their attention/focus is on something it's easy to trick anyone ( me the first! How many time i tweaked eq on the next channel on the console... lol, it happened to all engineer i know...).
 
Okay. Been talking to @oltos offline. One of the songs he is interesting in improving the sound of can be heard on youtube:

IME the youtube version in some ways may sound a little better than the version oltos extracted from a CD. Youtube version might sound worse in other ways though.

Anyway, given the youtube sound, maybe there was not any lossy compression used in the version oltos has. It sounds like a pretty bad recording to begin with.

Thinking about this some more gives a few ideas to try, maybe just one idea alone or maybe in combination with other ideas. Don't know what order of processing might be best if multiple ideas are tried at once.

Here we go:
1. put a notch filter at 300Hz. Adjust width and depth for best sound.
2. make two tracks of the file in a DAW, and HP one track at around 300Hz, and LP the other track at right around the same frequency. Process the the two tracks differently with EQ and or compression/expansion.
3. try a multiband dynamics compressor plugin that can also act as an expander. Play around with settings to see what you can do.
4. Try saving the file to MP3 or AAC with some lossy compression. Sometimes the lossy compression algorithm will remove some bad stuff from a bad recording and make it sound a little better. Have to experiment with bitrates and lossy algorithms to see what works, if anything.
 
What a truly awful recording why would anyone want to try and improve it? Sarcasm aside that YouTube clip sounds like the ex juke box discs I used too buy from the market in the 60s, all played to death. I would say the main problem with the playback in this clip is tracking distortion not helped by that brush in front of the cartridge, it looks heavy and I would guess is adding pre echo to the sound. If anyone is keen to hear a better version here is the 1997 remaster.
.

It sounds like an attempt at the Phil Spectre "Wall of Sound". Way too much reverb and flat dynamics. Good luck pitch shifting that one.