I have read other posts with this heading and notes that the solution in all
cases (until ours) is to recreate the user's profile.

We have created a new profile. We have removed and recreated all his
profiles. We also deleted his current OST files (he had a couple) and
unmapped all PST files. We have removed and reinstalled the entire Office
2003 Suite. In every trial, Outlook presents us with the same error message
every time.

An additional note: we had an Exchange server go down on Friday, and that is
when the user - who was on the affected server - saw this error. Since then
the server has come back up and all other 1500 users seeing this error
message are fine. Except for this one guy who continues to get the message
despite trying all we have tried above.

I had him log into another box, set up his e-mail account there, and he can
log in with no trouble, so the issue is clearly local to his computer.

I suspect it is a registry setting but I do not know which. Could you make a
suggestion perhaps?