Following advice here, I ran the unnamed MP3s through MusicBrainz and it found a lot of the filenames.
I then ran it over a lot of files dating from before the Jar was Broken and found some wrong names, got full album info etc.
A very useful link! Thanks :D