Had a similar problem myself recently. After changing ISP, I wanted to continue using my old mail, so, had to change connection, through the account, to the new ISPs connection.
Here is a cut&paste from Microsoft KnowledgeBase
RESOLUTION
To resolve this behavior, verify that you are using the correct account settings for your assigned e-mail servers. You can obtain the server information from your ISP or local area network (LAN) administrator.
To verify the settings for your Internet E-mail account:
Start Outlook.
On the Tools menu, click Accounts.
NOTE: If Accounts does not appear on your Tools menu, then you are not using Outlook Express 5.
On the Mail tab, click the name of your e-mail account, and then click Properties.
On the General tab, verify that your e-mail address is correct.
On the Servers tab, verify that the e-mail server information is correct for both the incoming mail (POP3) and outgoing mail (SMTP) servers. Verify that both servers have the correct settings for your password and account name. Ask your ISP if your server requires you to log on by using a secure password authentication and if your outgoing mail server requires authentication.
On the Connection tab, verify that the connection that you use is correct. For example, you may connect through a LAN or through a dial-up connection. Without a valid connection, your e-mail program cannot communicate with the e-mail servers.
On the Advanced tab, verify that your server ports are correct. POP3 servers use port 110 and SMTP servers use port 25. Verify that these ports are correct. For more information, contact your ISP.
Click OK, and then click Close to save any changes.
Sounds like you may have tried all this stuff already, but have a look, perhaps something has been overlooked. Hope some of that helps.
Good Luck