You might want to have a look here
http://www.bleepingcomputer.com/forums/topic131299.html and consider running the SDFix tool. It is designed to be run in safe mode.
Rootkits, by their nature, are difficult to detect and remove, and yes, they (and some other types of malware) recreate themselves, often assigning a random filename to the temporary processes involved.
It would make sense, once the tool is downloaded, to go offline while scanning, and run repeat scans while offline using MBAM and SAS as well.
You might want to print out the instructions at the page I linked. (It seems to be fairly straightforward, tho.)
You know SAS has a toolkit with some useful repairs. Might be worth looking into that once the malware scanners have done all they can do.
It might take a bit of persistence to nail this thing. It just depends how much you want to nail it, rather than re-install.