Outlook keep prompting for password

We have our POP3 mailboxes hosted by ixwebhosting.com. We use various versions of Outlook (2003, 2007 and 2010), which is configured to retrieve POP3 mailboxes. Outlook frequently pops up for password. We have to click on "ok" button a few times to get rid of it.
This happens a few times per day in the past few months from time to time.

This happens to all our users, to all Outlook versions. As a test, I configured a mailbox with Thunderbird and leave it running for two days, and i did not see this problem.

The hosting company said that there has been no problem with their mail server. It was our Outlook or firewall or ISP, etc

Our users are at different locations with different ISPs, how come they all have the same problem?!
I cannot confirm it is the hosting company's problem either, because Thunderbird works fine without this problem. So i am quite frustrated.

The hosting company asked me to follow these in Outlook configuration:
1) Username: username@mycompany.com
 2) Password: xxxxxx
 3) POP3 (Port 110) : mail.mycompany.com
 4) SMTP (Port 25) : mail.mycompany.com
 5) SPA (Secure Password Authentication): should NOT be checked.
 6) My server requires Authentication: should be checked
 7) Increase the connection time out to 5 mins from accounts properties,
 Also increase your Send/Receive time to at least 5 mins.
 9)Make sure you don't use firewall and your ISP don't block connection

I have done all above, but the problem persists.

The hosting company also mentioned "Please note that our servers are using "POP before SMTP" system". I had no idea how this affects Outlook setup.

Should I switch our host??

Any thoughts??

Thanks
Jack