You have at least 3 options - to find a company that claims to specialize in e-mail services, to get another VPS or just to get shared hosting. Of course you'll need to point your domain to the new DNS. I presume that you don't want to get another account with your VPS host, but at the same time you'd better stay with them if you are satisfied of the service they provide.
Google is good, but would cost more if i have over 50 email account. Does anyone know if the email hosting companies really give something that is worth paying extra for (i am not refering to exchange, only hosting)