Exchange 5.5 vs. Outlook 98 and Win 98SE

I am sorry for those who check out both the NT and 98 sections but I wanted to see if anyone knows about this here to.
"We have a MS Exchange 5.5 Server on a Win NT 4.0 SP6 box hosting everyone's email, we have a Checkpoint Firewall, and then we have a remote user using Win 98SE and Outlook 98. They go to use the Outlook 98 with the Exchange they get a "Can not connect with server" error. LMhosts is correct, because when we ping using the name of the server or the IP address it asks for the username and password for the firewall and then gives replys. When setting the account up under Outlook properties, it checks for the name when asked (asks for the username, domain name, and the password for their account) and finds the name. When you double click on MS Outlook it then tries connecting in, asks for the Firewall username and password, authenticates, (after this we usually have to hit retry due to timing out because of the firewall login/speed of the user) then sits and does some work, and then kicks out the "Can not connect with server".
Any ideas would be much appreciated. I am thinking that it has something to do with the Win 98SE but I am not sure.
Thanks"