quanto ao gmail não sei por causa de politicas de spam. Normalmente envio do meu host (e respectivo e-mail) mas primeiro tive que contacta-los para saber quantos e-mails o servidor deles envia por hora para poder ajustar as configurações.
Remetente pode ser teu mas com domínio corporativo. Geralmente funciona melhor.
Os melhores ESPs sugerem a certificação do remetente para SPF, Sender ID, Domain Keys e DKIM, modificando os registos de DNS do domínio.