Exchange server using Dial-up connection

I do a lot of work for a large company. They have a few people who travel with their notebooks and use them to access their mail on an exchange server. While on the network at their main office, they can acess it without any problems. When they try to access it using dial-up networking it does not find the server. After numerous attempts to make it work, I got it going, however they must click cancel at the windows logon screen for the dial-up connection to work. I had assumed that this would be satisfactory, however, it is not, I have been asked to fix this issue so that they can access the exchange server through a dial-up connection even when the windows logon password is typed in.
Has anyone seen this before? Any suggestions?