Exchnage Server 5.5

I came in this morning to my outlook clients asking for domain\username and password. 2000/xp clients. They are not allowed to login with any password. I have tried SP4, reinstalling 5.5, running the exchange optimizer, all useless. There is one techdoc associated with this issue, but there is not a link to a fix. Please help