Can you not create a view that includes all file types, and use Rename, Move, & Copy Files on that?
He could, just as soon as he's taken care of:
I wish all these files were in the library and properly tagged - so they would also move - but that is not the case currently.
Osho, if you want MC to manage the other files, they'll need to be imported and tagged.
The only other way I can see for you to get close to this without importing and tagging is to use the "My Computer" branch of the tree within MC. Changes made to the folder structure here should be applied to all files regardless of their status, so, browse, identify offending directories, then rename, or drag and drop, or whatever, and MC should keep the imported files up to date as far as its database is concerned, and move the files that are not imported also.
Do a test on a few unimportant directories first to verify that the results are good, then go wholesale.
-marko