I wouldn't be at all surprised if you somehow had all the files highlighted, and the popup box said something like "Are you sure you want to delete these files from your library?". The thing is, the dialog box has an unchecked box which says "Also delete these files from my computer". So, you would have had to check that box to actually delete them from the computer (and not just the library).

I'm not sure what MusicMatch does when you delete the file. I think it's a permanent delete (as opposed to Recycle Bin). I could check on this tomorrow. I assume you did a search of your hard drive to make sure it wasn't just moved or renamed.