Exchange Server un/available over T1

We just added point to point T1’s between a couple of our offices, and set up Outlook 2003 to connect to our Exchange 2003 server in the main office. Works fine, most of the time. I have 2-3 users though with a problem. When they first start Outlook in the morning it says “your Exchange Server is unavailable” and won’t connect. They keep hitting “retry”, and/or close outlook and start it up later, and eventually it connects. Once it connects, it works fine all day. Sometimes that retry process takes 5 minutes, sometimes 20. Sometimes it connects on the first attempt. I changed the server timeout to 60 seconds, but they got the “unavailable” error in less than 20. It doesn’t appear to affect everyone in that office, just a few of them, and it is sporadic. Any ideas where to start troubleshooting?