The best solution is to outsource your email to a provider who is 100% focused on being an email service provider. I've done a lot of research about this for myself and the people whose mail I manage and have been collecting my research on my IMAP Service Providers page, which is here:
I just updated this page yesterday so there are now 6 mail service providers that I recommend you try before choosing your mail hosting provider.
Also, you can tell your boss that it used to make sense to use the same provider for mail and web hosting, but this is no longer the case. The problem you are having is happening everywhere -- you are not the only one to have made this type of choice.
Good luck finding a good solution for your mail,
Infinite Ink ~ http://www.ii.com
Deflexion & Reflexion ~ http://deflexion.com