Check out Apisnetworks sometime. I've known the admin for a long time, he's been running that company forever. They are always very reachable and uptime has been superb. I host a few vanity domains and some other email stuff with him. It's a techie hosting company by a techie for techies. He custom built his own control panel software which is pretty comprehensive if you aren't comfortable with the DIY approach.
It is pretty cheap to just host email with them. If you wanted to swap web hosts then I suggest getting a custom quote as a site of this size/age would probably need very specific configuration to accommodate chatbear and etc.
If you are comfortable with configuration and etc then you can't go wrong with Amazon's hosting platforms.