Hosting said it's because of the fact that we are running nginx/varnish ?? They said they can't do big changes in that regard. They said they will look at it.
Everything worked perfectly when we first moved to this VPS, then DNS change and this happened. Thanks for the answer Slavik, but what exactly can I do to fix this, I have no experience in this matter. I have access to WHM and cPanel. Any help is greatly appreciated.