Just to add a 'me too' to the above. I came across the problem during an infestation with CoolWebSearch. Once I had cleared out all of the rest of the infection a stubborn 'kbdn.dll' remained in the System32 folder, constantly triggering Norton Anti Virus (which identifies it as the Backdoor.Agent.B trojan) but undeletable, and frequently undetactable, especially in Safe Mode. Every now and again it invents a new random .dll which tries to inveigle itself into Internet Explorer and change the homepage - WinPatrol is keeping that issue at bay for now, and I can delete the spin-off .dll files, but I've been having the same issues as gt93grad in trying to get rid of the trojan itself.
Since I've had the problem I've found it cropping up in forums everywhere recently. I'll give the fixes you mentioned a shot when I get back home - thanks for the tips; I was beginning to despair!