Hosting pro e-mail

Pěkný den,

hoster, u kterého hostuju jeden web, má na blacklistu aol.com a z této domény nám nedoručuje e-maily spolehlivě. Měnit hosting pro web se mi moc nechce, ale doručování z AOL je pro nás zásadní. Jak byste tuto situaci řešili? Hostovat jinde jen e-mail? Přejít s e-mailem na Google Apps, když stejně používá Gmail jako poštovního klienta?

Díky za nápady a doporučení.