If it's a CWS have you tried CWShredder? I had a system with a CWS and no matter what I did I couldn't remove it using all the methods you described and more. I tried that and sure enough it removed it completely from the system after a couple reboots.

I have since added it to my toolkit just for CWS variants, (in addition to multiple spyware/adware and virus scanners since one never catches everything).

Good luck, adware should be a fricken crime.