Update a few months later....
Digging up an old thread of mine to update whoever is interested...
A few months after I finished with this client (Nov. 2013), he calls me back that the PC has a virus. It was something Brontok or other, cleaned it out good, installed a full version of Kaspersky IS, Adblock+, Unchecky, verified everything was working at the office (I use Cablevision).
I checked his usual sites, The Wall Street Journal, Gmail etc., checked his Outlook, Windows and Kaspersky Updates, and everything worked perfectly.
I returned it to him and set it back up with his Verizon DSL, and sure enough the same problem reocurred: only Google and Bing sites work, and so does his Outlook email, but no search links and no other sites. Reset his modem, browsers etc, Tweaking AIO, nothing. My laptop connected fine, his computer can ping the sites, but can't load them.
To make a long story short, I plugged in a USB NIC and it worked immediately after installing it. So for some reason his built-in NIC was bad in a way that only allowed it to work at the shop, and only with Google and Bing sites at his home.
So +1 for those that suggested this, and in case anyone runs into some other oddball issue such as this, I suggest you try the USB NIC before wasting so much time like I did.