Этого достаточно, более того, всё корректно.
а) Received: from other-domain.ru (other-domain.ru. [123.456.789.0])
Это нормально, желательно что-бы nslookup -q=ptr 123.456.789.0 возвращал other-domain.ru.
б) From:
sender@my-domain.ruЭто нормально, никакой связи other-domain.ru с my-domain.ru быть не обязано
в) spf ... domain of
sender@my-domain.ru designates 123.456.789.0 as permitted sender
Это хорошо. Осталось DKIM для счастья.
А в спам попадает, вероятно, по желанию гугла, у меня внезапно все письма с @forum.firstvds.ru посыпались в спам.
3 года всё нормально, а тут пришлось фильтр создавать.
Некоторые BlackListы заносят в черный список сразу всю подсеть, а может вам "неудачный" IP достался.