Outlook isn’t updated with Windows 2004.
However, Outlook does get confused when there are multiple accounts and asks for passwords, you need to ensure you give the right username and password for each account (and click the remember password box). It has a habit of asking for the first username and password and then using that username for all subsequent accounts, you need to read what is in the dialog very closely, to ensure you have the right ones.
If that doesn’t work, delete the profile and create a new one, that usually solves the problem.
I had to set up a fleet of new laptops a couple of weeks back and each user had their own account, a sales account and an export account. It took a couple of restarts of Outlook, before it had all the passwords correctly associated. It is a pain, setting them up, but it all works very smoothly after that.
If Outlook loses its connection to the server, it can start asking for passwords again (timeout is somehow treated as a password failure), it has always done this. Closing Outlook and re-starting it is usually all that is required, it will reset the password failure and use the existing, saved password.