So, you are saying you ping the Exchange server by name and a different IP address is returned each time? What happens if you go to a cmd window and
<enter Exchange server name>
What information gets returned? If more than one address gets returned then it is possible that there may be some kind of load balancing happening. The other thing to check if you have administrative access on the Exchange server is if the NIC tcp/ip settings are for dynamic IP addressing or static. It should be set for static and the correct default gateway set.
You should also check your IP settings to be sure that you have the correct DNS server settings and appropriate gateway settings.