About ur story, there is no mention of any anti-virus either installed / not (100% I am sure it is there).... but have u ever updated its related files from their site.... u did not mention here.... "After I have restarted the exchange server and other users have either restarted their computers and/or Outlook, all users are able to send/receive e-mails just fine.", suspecting malware about these words, though not sure. Try to check ur systems with latest anti-virus / might be MS updates behind this issue as u mentioned here. Although it is usually happened due to cached credentials that will not update. Better it is needed to go into credentials manager through CP and delete the current set / update the settings to the correct password. I am not aware about ur settings, though u may check the virtual dirs for the correct authentication methods and make sure they r all OK. For better info see MS ref. Though it is based on OL 2007, but it can help u to the some extent.