I thought I'd recommend looking into using Google Apps For Your Domain for e-mail. Here's the link to the standard (read: free) version: Standard Google Apps.

It's hosting independent, so if you move in the future, you can just make sure the dns at the new server has the mail pointing to google's servers, and you should be good to go, with no loss of data. Plus it uses the gmail engine, which is pretty great and flexible. Here's info on setting up google apps with HostGator.