On every Exchange server reboot, on every client which has Outlook currently opened a new dialog prompt appears, asking for user credentials.
After the server has finished rebooting, everything goes back to normal, but most users have to enter their credentials at least one time again. Users which do not have opened Outlook during the server reboot progress are not asked for user and password afterwards.
There are many forum threads regarding this topic. Some users recommend to disable Outlook Anywhere or to change the Outlook authentication method. Nothing of those hints helped in my case.
For me, the best solution for me was to simply increase the server timeout in the Outlook Exchange account.
In Outlook 2010, open your Exchange account’s options and change server connection timeout from 30 to e.g. 999.
In your domain, you can e.g. distribute this setting by changing the appropriate registry value (in milliseconds, hex), deploying via GPO:
Maybe a reason could be that the Exchange Windows services take more than 30 seconds to stop on a server reboot, which might cause some service to invalidate the user credentials for a short time (this is only a guess).