Hi timestream,
You mean after server reboot, users need to authenticate every time (open Outlook) or only one time?
Since this issue not occurred on all the users, do you recreate Outlook profile to have a try?
Here is a related thread for you, hope can give you some help:
Outlook prompted for password after reboot of Exchange 2010
http://social.technet.microsoft.com/Forums/en-US/exchange2010/thread/467ec116-3bf7-4b6e-9705-b8a5fd8191a9
Thanks,
Evan
Evan Liu
TechNet Community Support
