Quite a few hours, spread over several days. It would have been easier and a lot quicker if the computer was physically in front of me. We wasted much time just getting the remote desktop to work.
Having said that, had I used the gmer tool to start with it would have taken a fraction of the time, even remotely, so it really does come highly recommended.
The tools I used were as follows:
Avast anti-virus
Malwarebytes Anti-Malware
Trend Micro HijackThis
Gmer.exe
Windows System Integrity Scans in the command line
Remove the offending file manually
Tried to remove the offending file using the command line as well and it wasn't having any of it
I think Juddie had also run online scans and Spyware Doctor
In the end I disabled system restore, unlocked and stopped the hidden process with gmer.exe, scanned and removed the offending file using malwarebytes (after I had confirmed it was a completely bogus sys file). Run a system integrity check to make sure there were no issues and then re-enabled system restore once all scans were coming up clean. Probably one of the most persistent things I've come across.
That probably means you have grounds to quote someone above and use your catchphrase