I know that there is another thread about this topic here on serverfault.com but it did not solve my issue.
I have also googled it and it seems that SPF record could be mis-configured in some cases but it did not help me neither.
Can someone tell please me why I am getting the "Reverse DNS is not a valid Hostname" error: http://mxtoolbox.com/SuperTool.aspx?action=smtp%3awebkonsulenter.dk&run=toolpage#
Thank you very much :-)
webkonsulenter.dk. 3600 IN MX 10 mail-hosting.dk.
, the A record for MX host:mail-hosting.dk. 3598 IN A 85.114.139.44
and the reverse lookup:44.139.114.85.in-addr.arpa. 86400 IN PTR mail-hosting.dk.