Wrong domain gets mapped if transferred within the network

I have a site which was upgraded and we changed everything for it. In order to keep it online, we created a new sub site and when we were finished we removed the mapping from the old site and put the domain info on the new site under Tools>Domain Mapping.

If I am logged in, I get to the right place, but everyone else gets directed to the old site. This is a very serious issue.

The network has W3 Total Cache enabled. I have rebooted the server in order to clear the APC Cache but to no avail.

Please let me know how to resolve this issue as fast as possible.

Thanks A.