Du skriver jo ikke noget om i hvilken forbindelse brugerne skal modtage en mail.
Har du fx. installeret et plugin som sender en email? (kontaktformular, SMTP plugin ect...)
Det godt være noget med din host at gøre, ell. dvs opsætning i php.ini.
Du skriver at der bliver sendt email, og derfor kan jeg godt forstå din Hoster - de sender mails - derfor er problemet relateret til din løsning.
Det første du skal sikre dig, er at mail afsenderen ER oprettet på din server. (det kan blot være et alias for en eksisterende email)
Du bliver altid greylistet (eller blacklistet) som afsender, hvis du benytter email-adresser som ikke findes på serveren.
- hvis du fx. har lavet en fiktiv "svar-læses-ikke-kun-til-information@domæne.dk" addr.
Hvis det er et plugin, kan det være at der er knas med HTML formatet, at der er et problem med mail headeren osv...