SPF=pass, но записи TXT к домену в DNS нет. Как такое может быть?

1. никаких записей нет.
2. я тестирую на получателе который жестко проверяет именно запись в DNS.

единственное что меня смущает, почтовик который формирует письма, имеет шифрование, в заголовках эта видно (UNKNOWN:AES128-GCM-SHA256:128)
может быть дело в этом?

iantoshkin: покажите заголовки полученного письма, иначе гадание на кофейной гуще получается.

Есть еще вариант что вы смотрите не туда. SPF проверяется не по From: письма а по envelope-from SMTP конверта.

у них домен одинаковый.

Authentication-Results: st15.mi6.kiev.ua;
spf=pass smtp.mail=webmaster@mydomain.com
Received: from kvmde11-7634.fornex.org ([5.188.15.55])
by st15.mi6.kiev.ua with esmtps (UNKNOWN:AES128-GCM-SHA256:128)
(Exim 4.80.1)
(envelope-from )
id 1cA0Ca-0000MU-AM
for bigger@ua.fm; Thu, 24 Nov 2016 22:01:00 +0200
Received: from cricketuser by kvmde11-7634.fornex.org with local (Exim 4.86_2)
(envelope-from )
id 1c9zZe-0001et-JG
for bigger@ua.fm; Thu, 24 Nov 2016 22:20:46 +0300
To: bigger@ua.fm
Subject: =?windows-1251?B?wu7x8fLg7e7i6+Xt6OUg7+Dw7uv/?=
X-PHP-Originating-Script: 501:Site.class.php
From: noreply@mydomain.com

домен изменил.

iantoshkin: измененный домен мало чем поможет, к тому же все что в угловых скобках потерялось. Хотя бы в личку напишите.

Ничего вам не скажет это. Домен я регил самостоятельно - никаких прописок кроме A записей не делал. Более того, домен не один, а два. Оба регились у разных регистраторов. Но они завязаны на одном и том же хостинге. Всмысле для каждого домена свой VPS от одного и того же хостера. Из коробки они предлагают настроенный exim. Единственное о чем я думаю, это то, что они каким-то хитрым способом настроили почтовик.
Я не первый день работаю с spd, dkim , dmarc - настраивал 2-3 раза для разных серверов.

Но столкнувшись с таким, не понимаю как это работает.

ах да, хостинг с регистраторами не связаны.