It vaguely sounds like something along the lines of Newdotnet. I haven't kept up on it because I don't work in DNS anymore, but it used to basically hijack DNS routing to put traffic through their servers so you could see domains using TLDs that they were selling, like .shop, .xxx and other TLDs that aren't actual ICANN registrations.

Not remotely saying that's the problem. Like I said, that's how it USED to work, and at a glance it doesn't look like much has changed, however it could be something else entirely. But if a program like that screwed up DNS routing and then was corrupted or removed incorrectly, it could cause issues like that.

http://en.wikipedia.org/wiki/New.net

http://www.pchell.com/support/savenow.shtml