Você mencionou o Google Apps, que é uma solução viável. Você definiria os registros MX de seu domínio para que apontassem para o Google (eles tinham instruções para isso) e Para o envio, você simplesmente configuraria seu aplicativo PHP para usar as credenciais da sua conta de e-mail do Google Apps. Os e-mails parecerão ser enviados a partir da conta do Google Apps.
A outra opção é você pode instalar um agente de email no seu VPS. Boas escolhas incluem Postfix e Sendmail, que estão no repositório CentOS. Configurá-los para receber e-mails é muito mais difícil do que simplesmente usar o Google Apps (ou outra solução hospedada), mas factível; configurá-los para enviar e-mails é fácil, mas provavelmente não é confiável, pois você provavelmente será bloqueado pelos filtros de spam dos seus destinatários. É melhor confiar em outra pessoa para entregar sua correspondência.