Wenn die einheitlich waren und Du die aus den Tags ableiten kann, nimm MP3Tag damit sollte das recht einfach und mit ein paar Klicks gehen.
Kleiner Tipp, Du kannst komplette Verzeichnisse mitsamt unterverzeichnissen laden.
Die Dateinamen wurden ja verändert und die heißen ungefähr so:
Trance 80's (The Next ___on of Trance) (disc 2)-17-Gigi D'Agostino-The Riddle.mp3
Da kann ich nicht besonders viel mit Mp3tag machen 
PS. Das Programm kannte ich schon
Naja, das kann halt auch Dateinamen aus Tags bilden. Wie war denn die Syntax des Dateinamens vorher?
Die Syntax war Interpret - Lied, wenn du das damit meinst
Also vorrausgesetzt, die Tags sind richtig, lädst Du alle Lieder in MP3Tag, markierst sie, drückst Alt+1 und gibst
%artist% - %title%
ein und das sollte es tun.
Aber irgendwie glaube ich, dass ich Dein Problem nicht ganz richtig verstehe,
Dankeschön 
Es hat funktioniert
