¿Has identificado porqué van a correo no deseado esos correos? ¿Tienes el registro SPF activo?
De todos modos si varios de tus usuarios marcan "esto no es spam" en su proveedor de correo electrónico los filtros aprenden de esto y consigues que en poco tiempo tus mensajes no lleguen a spam. Siempre y cuando no estés en ninguna lista negra ni nada por el estilo, claro.
¿Has mirado
Amazon SES? Es el servidor SMTP de AWS, tal vez te sirva para enviar todo tu correo desde esta plataforma. Pagas por mail enviado (en tramos de 1.000), si no envias no pagas.