How can I permanently remove a seemingly stealthy ad-ware installer?

Solution 1:

If your system once has been compromised, there is no way to trust it before completely wiping it.
Also you should change passwords (PayPal, eBay...).