Eu passei pelo mesmo na minha última empresa e não há informações do Gmail sobre isso (para falar). Felizmente eu sou amigo de algumas das melhores pessoas de entregabilidade de e-mail no país, então essas dicas podem ajudar:
Em primeiro lugar, o Gmail parece penalizar novos domínios. Não há nada que você possa fazer sobre isso, mas continue enviando e-mails e espere que isso desapareça eventualmente. Registre seu domínio em qualquer lugar - Google Analytics, ferramentas do WebMaster, indexe sua pesquisa e seja exibido no Google. Blog sobre isso.
Em segundo lugar, sim, peça a seus usuários para colocar você na lista de permissões. Quanto mais pessoas fizerem isso, menos provável será que o filtro global do gmail o odeie.
Certifique-se de que as coisas estão formatadas corretamente: parece que tudo está aqui, mas fomos pegos por coisas como um cabeçalho de ID de mensagem formatado de forma fraca.
Cuidado com palavras como "Grátis". A capitalização é importante para o Google também, então "free" não será pego como ruim.
Adicione a formatação estendida de Para e De, ou seja, nome completo entre aspas e o endereço entre colchetes angulares: "João Silva"
Espero que essas dicas ajudem. O Gmail não é muito transparente sobre essas coisas. O primeiro ponto é o maior problema e impossível de contornar.