These problems seem to point to the Virtual Server(s) and potentially DNS. While you can certainly take a look at the settings, I would not change anything to boot — particularly, if the default settings are still in place.
The first thing you should do is ensure that the Windows OS and Exchange Server are both patched to the latest service pack, hotfix and patch levels. You will want to install all security and critical updates and recommended updates, such as drivers and performance enhancements at your discretion.
Then I would run the Exchange Best Practices Analyzer (ExBPA) and Exchange Troubleshooting Assistant. You can download both from here – Microsoft Exchange Server Analyzer – Articles.