It's very pervasive. It probably installed itself as a proxy, and you didn't tell LWP to use a proxy.
I just had to clean that nasty bugger. It involved booting from the install CD and renaming/deleting all the files with names like "fjsdahds.*" (i.e. an eight(?) char string of random letters and numbers) in c:\windows or was it c:\windows\system32. Miss one and you have to start over. This is aggravated by the recovery console's dir's inability to recognize the /od option. Finally, clean all references to the files you deleted from the registry.