Pues es bien curioso. Esperemos a ver si el experto en Plesk aparece por aquí y te da alguna luz al respecto.
En el entretanto, me pregunto qué te han dicho los administradores del servidor (dices que el servidor es administrado) y qué te han dicho los de soporte de Plesk.
Por aquí divagando, podría aventurarme a decir que quizás tiene que ver con qmail-default:
Tracking spam origination using qmail and vpopmail
pair Networks - World Class Web Hosting - E-Mail - Using Qmail
Por cierto, hace más de 6 años alguien preguntaba lo mismo que tú y no recibió respuesta:
FAQTs - Knowledge Base - View Entry - When some sends an email to my server running qmail my server inserts random domain headers
Saludos.
