Check the outlook configuration , whether is it MAPI/ POP3/ RPC/HTTP.., and also check the mail box size of those particular users.
Try to reconfigure the outlook profile and also check system DNS and IP address details..if everything is fine. then do the follwing step.
1. add exchange server IP address or Host name in Host file (c:\WINDOWS\system32\drivers\etc\hosts)
then u will be able to connect the server faster