|do a ping microsoft.com|
do a tracert microsoft.com
what are the results?
clean installs won't solve your issue if the first clean install didn't.
what changed recently? recent reconfig of a software firewall/antimalware software? Didn't go into the router and do a domain restriction?
IE8 and service packs are just fine fyi.