from what i understood the files were just renamed , so why did you even try data recovery softwares? they didnt got deleted , simply load em youll see the ID3 tags and start renaming back.. and if the tags got changed too then i hope you got good memory
edit mediamonkey dont have an undo function?