Exchange problem with only 2 users

I have an exchange 5.5 setup where all my users except 2 travelling notebooks are connecting to mail using Outlook. The two notebooks came back from a trip yesterday and couldn’t get outlook to open. They connect fine to the network and can get toall resources. The configuration in networking matches all the rest of the machines but if I go in to the exchange setup and try to validate the name it never finds it. If I put the same users account on another workstation I get right in and connect using outlook to that exchange account. Any ideas of where else to look? IP’s are dynamic, WINS is disabled (on all machines), gateway is dynamic, DNS is enabled.
Thanks