El problema es que no logro hacer que los mails no vayan a spam folder, y en gmail simplemente ni siquiera llegan los mails.

Esto se debe a la manera en que se envía el mail, al servidor smtp que estoy usando el cual es mi propio dominio vamos a llamarlo mail.extreme69.com o al contenido en body del mail?

El hosting es super hyper shared, así que calculo que podría estar en banlist por ip, pero sería ridiculo que lo hicieran por ip y no por dominio ya que yo no tengo la culpa si otro idiota con esta ip spameó o algo.

Si, aunke suena sumamente estúpido no probé con otros dominios, voy a probar y les cuento