Mail problems after restore - help!

[RandyL712]

We just restored every domain on the server from backup, and about 10% of them (so far reported) can't send email using Outlook Express.

We have mail authentication checked, and have confirmed the usernames and passwords are correct, but when trying to send mail, OE repeatedly asks for the username and password. Webmail seems to work fine.

Changing the password in CPanel doesn't fix the problem - the only solution I've found that works is to delete the mail account in Cpanel, and re-add it as new. Obviously I can't do this for every email account in all these domains.

Any ideas? I've done the mailperms fix, the fixmailman script, and I'm stumped. I have some really irritated customers and I'd really appreciate any help you can offer.

EDIT: Helpful techs at my hosting company have informed me that I don't need the Authentication box checked. Without it, the problem goes away. Strange though, they were the ones who told me we NEEDED it checked two years back (And why do 90% of the accounts not have an issue with it being checked?)