Webhost blocking my IP address + POP 3 problems

Hi,
I hope I am in the right area for this. I would appreciate help on a couple of problems which may be related.

My boyfriend and I have several websites hosted with a company, using one main domain and several add ons each with multiple email addresses set up on them. In case it's relevant we are using desktop PCs with Windows 7 and Office Outlook 2007 plus our ISP is separate company also.

Until recently everything has been fine but a problem has begun where emails are not coming down from the server. Through a long trail of help tickets with the host company, they said the IP address was blocked due to the IP address attempting access multiple times in a minute. This is not something either my partner or I are doing so we ran virus and malware checks but came up empty. To aggravate the situation the host company's support is not good at all and it's obvious you're talking to someone with a list of set answers, i.e. not engineers but remote workers in Asia somewhere. They say they have unblocked the IP address (this has been going on for 4 days now) 1 or 2 emails then arrive and then afterwards back to receiving nothing again. Outlook periodically displays the error message 'Unable to connect to POP 3 Server please contact your ISP or server administrator........' etc, against each email account. Sometimes through cPanel and on Webmail, some emails are there, but sometimes not. But they don't make it to Outlook from the server at all. The host company keeps saying the problem is fixed. It definitely is not.

Any suggestions to help fix this would be really welcomed - sorry for the long and wordy thread but it's complicated to explain.

Many thanks for reading
JulesM