dns kayıtlarınızın tamamı doğrumu?
Özellikle mx kaydı.
Eğer vps de birden fazla ip adresi varsa ve sizin mx kaydınız ile maili gönderdiğiniz ip adresi farklı ise yine problem olabilir.