If the 1st one didn't work, then try video-fixer. Despite its name, it can apparently also fix mp3's. At least have a look at it. Perhaps these utilities are not the saviour after all. But there's only one way to find out. Unfortunately I use a mac & those apps are only for windows.

Try expanding your search. Use a general search instead of an audio search. Just try the title or just try the artist. Even abbreviate it or slightly mispell it. There's lots of people who don't label their files properly.