Could you tell me if your problem has been solved?
This could be due to DNS failure.
Changing DNS server to Google DNS or OpenDNS, or remove all cookies and cached files on your browser will help to resolve this issue immediately. Since you already removed history, cookies, cache, etc try to change the DNS.
This is probably due to your system's DNS settings - can you please confirm that the DNS is current and working as expected? If this is just happening now and then, you might be in need of opening a ticket to see if Microsoft can help you track down the cause of the issue.
Did I answer your question? Mark my post as a solution!
Proud to be a Datanaut! Private message me for consulting or training needs.