A customer of ours has Office 365 Exchange that was migrated from BPOS a few months ago. One user had this issue up front but not others; recently after passwords expired and were changed, several other users began to get continued password prompts (relating to a RED001... server, the old BPOS server) in Outlook shortly after it opened, even though it was connected to Exchange and getting new email and such just fine. The password prompts were very annoying.
Additionally, if I did a Repair from Account Settings, the account would fail to autodiscover one time after a timeout, but if I retried immediately it would succeed the second time (DNS was configured correctly). After the fix below, Repair succeeds with autodiscover the first time every time, and quickly.
I tracked down a blog post where the first comment gave me an idea. I tested it and it seemed to work, so I expanded it a little into a complete solution that has solved the problem for this customer, I'm sharing it here in case it's useful to someone else:

In order to fix the random password popups with Outlook where BPOS was previously installed, navigate to this folder in Windows Explorer(the %userprofile% text will be replaced by Windows automatically with the correct path):

%userprofile%\AppData\Local\Microsoft\Sign In\Config\

Then go into the subfolder that's named after the Outlook email address.
In that folder, rename or delete these two files:

ConfigurationParameters.xml
outlook-autodiscovery.xml

Close (if open still) Outlook and then reopen it, and go to Tools menu (Outlook 2007) or File menu (Outlook 2010) and click Account Settings. When viewing the account (should only be one), click the Repair button just above the account list. Click Next to go through the wizard which should be successful all the way through, then close out of the settings, restart Outlook and the password prompts should be gone.
I specifically tested this with Outlook 2007 but I assume 2010 would be similar. I suspect the files above are remnants of the BPOS sign-in assistant (which I think had been uninstalled, though maybe not fully. However I forgot to double-check this before disconnecting from the customer's machine).
Hopefully that helps someone else! I was unable to find much useful information online; the link I did find above didn't have a complete solution just a suggestion in a comment I ran with.