This might seem obvious and there might even be a better way to do it, but to find all files in a directory that don't match a specified regex just find all files and grep out those that don't match.
So if you want to find all files in dir/ which don't match ^.*\.mp3$ issue:
find dir/ -type f | grep -v "^.*\.mp3$"
-type f forces find to only return files (no directories) and the -v inverts the results of grep.
One thing to be careful of is that now the regex is applied to the entire paths returned by find. Not just the name of each file.