Por supuesto, debes de tener un dominio para tu servicio de correo. Ese dominio estará en un servidor DNS donde se define tu zona. Si no tienes el control de tu zona debes de comunicarte con el proveedor que te asignó tu dominio e indicarle que en sus servidores DNS incluya en tu zona la línea:
midominio.com. IN TXT "v=spf1 mx ptr ~all"
Le dices que es para SPF (Sender Policy Framework).
entiendes?
No sé si esto solucinará tu problema pero nosotros lo resolvimos así.