אי יכולת שליחה - בגלל (לפי מה שאתה מסביר) ששרתי הדואר שלך לא יכולים לדבר עם שרתי הדואר שלהם
אי יכולת קבלה - בגלל ששרתי הדואר שלך לא יכולים לדבר עם שרתי הDNS של הדומיין הרלוונטיכדי לפתור את הבעיה הראשונה, תצטרך Mail Relay במקום אחר בעולם, לצורך העניין שרת VPS פשוט בעלות של פחות מ10$ לחודש יעשה לך את העבודה.
כדי לפתור את הבעיה השניה, ובהנחה שלבטל בדיקת SPF+PTR זה לא רלוונטי, אתה צריך להשתמש בשרתי DNS "פתוחים" כמו גוגל וכו', ואם כבר יש לך VPS, תוכל להשתמש בו כמובן.
כמובן שכל זה די בגדר "ניחושים", כי בלי לאסוף נתונים אי אפשר באמת לראות מה קורה, קשה לי להאמין שהספק "תופס פאקטים לפי הדומיין".