As far as I know, Microsoft.com is hosted on IIS 7. If you can access that site from a Linux client, I think the horrible case you mentioned only exists inside your network.
Please narrow down the problem first, and then draw a new conclusion. Possible approaches are,
1. What about setting up a simple HTML page and access it from all clients? Does the problem happens?
2. Is there any abnormal thing happening on the server when the problem appear? Is the w3wp.exe using high CPU or high memory?