Some modules require a specific MS runtime DLL - if you don't have this on your system they'll complain about not being "found", even if they are there. There are other potential causes, but that sounds like the most likely one.

As far as cleaning out old modules is concerned, NetLoadModule makes this pretty easy. Just blow away pretty much everything in your Modules folder, unless you're using it with your current theme. When you recycle or load a new theme, any missing modules will be DL'ed and reinstalled. Think of it as an NLM enema.