Les is correct in that if the Proxy is not found, they can not get to the internet at all. I have verified that the GPO is being applied.

When I get back into work I will look at the binding orders and protocols. And there are multiple NICs, however one side is for NLB and the other is primary. The primary is ordered first.

What has me confused is that when using Proxy at a desktop it works as expected, and if I take out the proxy at the TS, it works as expected. But as soon as I add Proxy to the TS, it is having the problem. Which in my logic points at the issue being the Proxy, but maybe it has more to do with IE and the way it works in TS mode.
_________________________
Today is the tomorrow you worried about yesterday.