I actually don't know if the recovery disk will be drastic enough. Some part of the Windows reinstall must include a format, to wipe all files from the disk. I've never had a computer with OEM operating system installed; always had the Windows installation disk, so I don't know about using recovery partitions, sorry.
You might want to try some of the apps listed
here. I'd look at trying Rootkit revealer (by Sysinternals, one of the original anti-rootkits), Rootalyzer, by the makers of Spybot, and maybe F-secure's Blacklight.
Thing is, you will probably need advice before trying to remove what is found, as there are often hidden objects that are quite legitimate. It definitely is not safe to just delete anything found. (Even if you can.)
I'd also keep updatting MBAM, and run it again. It's pretty good on these (from what I read) if it can detect them.