What is left now is how to determine which samples are clipped and which are not. For these samples it's easy (I clipped everything at the same level). That's also what you get when you directly rip a CD. But in MP3s things may look very different.
Bojcha: About Nelly Furtado track: This thing has 'Tilt' again...
Anyway, I tried the following:
1. Boost the volume by 50% (this introduces a lot of extra distortion)
2. Then pass it through Stereo Tool's declipping filter
Result seems to sound slightly better than the original this way. So if I manage to get the distortion detection to function properly (handle tilt) it should really improve.
I've also tried Katy Perry - Firework, but I don't even see any clipping there

Still it sounds horrible.