Google's Desktop Search, for one, does some weird hokey in the OS kernel to intercept outbound TCP port 80 connections (such that it can insert Google Desktop results in Google Web searches). It's entirely conceivable that some other sort of evil application could be patching into the same hooks.

To try: telnet to port 80 of some web server by hand (or via a bland tool like wget or curl) and see if you can make that work. If it works, then blame the proxy settings. If it fails, then ponder the spyware and consider something as painful as reinstalling the system.