Any ideas where i can get a service that will receive and store my mail whilst my server is down ?

Your upsteam ISP should be able to offer you this service. Usually, instead of saving your mail what they will do is configure sendmail to automatically resend your mail every so often until your server comes back up, or the time limit expires (usually after 3-5 days).

To do this you created weighted MX records in your zone file. Your mail server has the lower wieght and is given priority, while your ISPs mail server has the higher weight, so it is only used if your server is unreachable.

Check out www.smartbackups.com The owner is a member of WHT and seems to know what he's talking about.

I use zoneedit.com for a couple of my domains. I use zoneedit.com as DNS for the domains, and if my mail server is down, zoneedit.com stores the mail on their server until my server is restored.
I've never had to use it, but it's there.

Thanks for the help guys