Need a Mail Host (advice needed)

Power outage on sunday took down one of my servers. The last remaining M$ server I had (which handled all my email routing and what not). It houses email for 5 domain names (the rest of the domains I house don't require email routing).

So the HDD took a crap after the power outage, and I have been trying to configure Linux-Debian for email (tried many different solutions, many different combinations, and I am just sick and tired of trying)....

I need a host that I can park the email at (not the web pages, just an email server that can host the email accounts of all 5 domains).

Any suggestions on good companies?

How many accounts is that ?

about 2 accounts per domain name, usually a webmaster@domain and a private account that person uses user@domain.

The way I did this in the past was to go for a cheap monthly account with a web host, (I used 1and1, home account £4.99 a month) and then just set up a set of email addresses on there for external domains.. 1and1 where one of the few I used which allowed multiple domains on the same account.

I just pushed the email there using MX records (can't remember the exact details, it was a while ago).

Not sure if that helps, may be worth dropping them an email.
There are probably other companies with similar offerings

One other "outside the box" idea is to download "vmware player" and one of the email virtual appliances eg. http://www.vmware.com/vmtn/appliances/directory/542 to run on it... instant mail server with spam trap etc, I've heard it runs quite well.