We just recently had this issue with SBS 2003 Premium and the solution is as follows:
In IIS the ExchWeb virtual directory must be configured to allow anonymous access under Directory Security -> Authentication and access control.
The problem is that something (ISA?) that gets installed changes the IUSR_<SERVERNAME> password or stops Windows from managing the IUSR_<SERVERNAME> password correctly. If you change this accounts password and specific the new password in this location that should fix your problem.
So you are right Atreyu.
