I think I found the problem to this. Our VPS's are setup to use one of our servers as the DNS resolver for all domains it connects too. So when we are having DNS problems it affects the VPS performance too.
I am going to do some things later so we can move away from these resolvers by setting up one on our VPS server and they will use that.
If it is a problem again do let me know.