devi fare delle prove/test aggiungendo/modificando gli headers inviati.

Il problema non è facilmente risorvibile perchè, come tu stesso hai notato, dipende dalle specificità del gestore di posta a cui è indirizzata l'email.
Ergo:
- non esiste UNA soluzione valida in termini generici;
- ciò che è "soluzione" per un gestore di posta non lo è per un altro.