Why does my laptop users' Outlook Out of Office refuse to connect?

Hi all,

Recently, I've had a rash of issues with certain laptop users not being able to set their Out Of Office auto replies.  We've found that if we wipe out their user profile, this issue goes away for a small amount of time, but then rears its ugly head once again.

My question is this:  Is there some underlying problem with my server?  I've read things about "autodiscovery in dns" and other things about sizes of mailboxes, etc.  I was wondering if anyone had some concrete things I can try?  I know enough about Exchange to be dangerous, but I'm no expert.

Any thoughts?

Thanks!