If deep scan is still not removing, here is some additional removal help:
From Chuck:
CoolWebSearch is a constantly mutating major nuisance. The best tool to
diagnose it is HijackThis, and expert advice. HijackThis shows all possible
traces of software, anything that MIGHT be malware, and lets an expert
identify the bad stuff manually.