As found out debugging the issue together with the original poster, the problem of DNS failing to resolve is that the VPS provider instated and warned previously about a policy obliging to use an internal DNS address, blocking the use of alternatives in their firewall.
As the OP had the email of the provider warning of the change, it was not necessary to do further debugging to confirm the suspicion.
It is rather common practice to force hosted services or servers to use internal DNS servers, to best monitor the usage, enabling earlier detection of compromised machines doing DNS denial of service attacks, to track better customer problems, give them access to special services, applying policies at DNS level (anti-malware, others), do request rate control, and even statistics.
Often malware also changes the default DNS servers of compromised hosts, and this infra-structure setup does not allow that.
Even without forcing all the customers to change addresses, firewall rules can be done, and are more often configured in VPN services and at corporate level to redirect all the traffic to external DNS servers to an internal one.
I would also add that often, as a current practice in the industry, while internal DNS are forced in customers in the lower tiers of service, it can happen that changing to higher tiers (e.g. paying more), that restriction is lifted.