I just ran into a very similar problem with a difficult to remove BHO: req.dat.
I contacted Macafee / NAI. It turned out to be this new "backdoor.cpk" thing. I am pretty sure I got it through a web advertizement via NetStad on Tuesday.
More information on the specific thing here:
http://vil.nai.com/vil/content/v_132432.htmI would give the MacAfee 14 day free trial a go -- hopefully it should result in you having a perfectly clean PC afterwards like mine.
-ben
Damn...Thanks I'll try that, hijackthis just isnt removing it..