Genau, wie Android sagte. Die meisten Mailserver überprüfen bei einer ankommenden E-Mail ob deine Domain, z. B. test.de, über die die Mail versendet wurde, einen korrekten MX-Record auf deine IP hat und ob der Reverse-DNS-Record zu deiner IP auf die Domain verweist, also ob test.de in deine IP und deine IP in test.de auflösbar sind. Wenn das nicht der Fall ist, nehmen viele große Mailanbieter Mails von deinem Server garnicht erst an.
Den Reverse-DNS-Record kannst du im Normalfall im Webinterface deines Serverhosters ändern. Sollte dir das nicht möglich sein, würde ich dir empfehlen deine Mails über einen externen Server weiterleiten zu lassen, gibts bei den meisten Mailserverprogrammen ne relativ einfache Option dazu. Dafür kannst du dann z. B. ein Googlemail-Konto verwenden. Direkt bringt dir das ohne korrekt gesetzte Records halt nicht viel, da deine Mails, selbst wenn sie vom Mailanbieter angenommen werden, zu 99 % direkt als Spam eingestuft werden.