Jeff,
I wasn't getting that error so I'm not sure if my troubleshooting will help... But you never know ...
I tried rebuilding the Outlook profile. No help; still getting prompted. Putting in the password didn't work.
Cleared the password forms and cache in IE and got prompted (which is what I expected) but entering the password still didn't work.
I then checked the zones like you did. All systems were populated in the right places so I removed them and readded them; got prompted again and was able then able to log in.
Obviously, this person will have issues again in 29 days when his password expires so at least this is a work around. I can log into that person's account just fine on my machine and the Vault system so the next thing I'm going to try is rebuild the Windows profile. I might force the issue by making the person change their password so it conflicts with where the cached information is being stored.
I'll keep you posted. Thanks for your help, we'll get this yet! ;)
PM