We've had an semi-full outage of Internet in the company. After some investigation it turned out to be that QualityNet is having problems with their DNS servers along with some routing issues.
They have advised us to change the DNS servers to new ones.
Old DNS Servers:
New DNS Servers:
These changes are permanent.