Check if the working mp3 have a xing tag. Did you create the old mp3s with audio catalyst?

Edit: The Xing/Helix MP3 encoder may be worth a try.

I do not have any old mp3-s available that i used to have in the nineties and early 2k. And that time i used Napster. Never heard of xing tag.

I believe Audacity uses ffmpeg or LAME.

The Xing/Helix MP3 encoder was popular in the 90s in Audio Catalyst, but now Xing/Helix is opensource.

Also various FhG, which you can use when you export a wav to mp3 with Windows media player or virtualdub if I remember correctly.

I used foobar2000 a couple of weeks ago to convert some files to mp3 to test Winplay3 on a 486/66. 128bkps was a bit too much though. It played fine with a little lower bit rate (96bkps?).

With WinPlay3 16-bit 2.3b5 in Win 3.11 dosbox-x, I was able to play FhG, Helix, and LAME mp3s encoded at 128 CBR, 44.1 KHz stereo properly.

Ah, I remember WinPlay3!
If memory serves, it didn't support midern ID3 tags properly?
Originally, ID3 tags were added to the end of the file, but this was bad for streaming (web radio).
So ID3v2 moved the tag to the beginning of the file (header).
Having both tags works, too, doesn't it?

It can play 192khz/44.1, though I suspect that it isn't VBR-compatible.

Ok. I ask, I answer. I used LameXP batch conversion program. Stripped ID3 tags. And it even plays low bitrate and variable bitrate by the way. Even Windows XP can run Winplay3. So the problem seem to be those modern ID3v2 tags. Original ID3 tag is supported and it even shows the information in Winplay3.