Emails from Hotmail to our domain always bounce

Now this is a rather odd problem with emails from any hotmail address being bounced by one of our domains.

First off, I can guarantee that this is not a spam filter issue as there is defintitely nothing being held, furthermore, the spam filter has no records of the emails ever reaching them. Secondly I can assure you that email from all other domains gets through just fine. Thirdly, I'm content that all of the DNS records are set up correctly with the MX record for the domain in question definitely pointing to our mail server.

I'm seeing some old reports of similar things happening with the gist of this being that Hotmail attempts delivery to the server hosted at the a-name record for the domain instead of the mx-record. If it finds a service on port 25 then it'll attempt delivery there. If not then it'll 'fall back' and finally look at the mx record. Can anyone confirm that this weird set up is still happening?

Has anyone come accross similar situations?
Any ideas on what else I should be checking to ensure that emails get delivered to the correct server?

Thanks for helping, Rob

Email Header

x-store-info:D6taffyBScEUZsL+ZXbbDvsjG9szfvD7
Authentication-Results: hotmail.com; sender-id=pass header.from=postmaster@mail.hotmail.com; dkim=none header.d=mail.hotmail.com; x-hmca=pass
X-SID-PRA: postmaster@mail.hotmail.com
X-SID-Result: Pass
X-DKIM-Result: None
X-AUTH-Result: PASS
X-Message-Delivery: Vj0xLjE7RD0wO0dEPTA7U0NMPTk7bD0x
X-Message-Info: AuEzbeVr9u5fkDpn2vR5iCu5wb6HBeY4iruBjnutBzpStnUabbM/X3OHG1tkHI7a3kMiU15mwZkdItk0fkPUd26iJME4hbgAR+RCB0ejIvg=
Received: from blu0-omc3-s1.blu0.hotmail.com ([65.55.116.76]) by BAY0-HMMC1-F6.Bay0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4900);
     Wed, 23 May 2012 02:54:43 -0700
From: postmaster@mail.hotmail.com
To: robforrest123@hotmail.co.uk
Date: Wed, 23 May 2012 02:54:43 -0700
MIME-Version: 1.0
Content-Type: multipart/report; report-type=delivery-status;
    boundary="9B095B5ADSN=_01CD299C0888E07C001CA7A1blu0?omc3?s1.blu"
X-DSNContext: 7ce717b1 - 1196 - 00000002 - 00000000
Message-ID: <Tx2NT7VXF000c8d13@blu0-omc3-s1.blu0.hotmail.com>
Subject: Delivery Status Notification (Failure)
Return-Path: <>
X-OriginalArrivalTime: 23 May 2012 09:54:43.0474 (UTC) FILETIME=[140FC720:01CD38CA]

This is a MIME-formatted message.  
Portions of this message may be unreadable without a MIME-capable mail program.

--9B095B5ADSN=_01CD299C0888E07C001CA7A1blu0?omc3?s1.blu
Content-Type: text/plain; charset=unicode-1-1-utf-7

This is an automatically generated Delivery Status Notification.

Delivery to the following recipients failed.

       #################@##########

--9B095B5ADSN=_01CD299C0888E07C001CA7A1blu0?omc3?s1.blu
Content-Type: message/delivery-status

Reporting-MTA: dns;blu0-omc3-s1.blu0.hotmail.com
Received-From-MTA: dns;BLU161-W65
Arrival-Date: Wed, 23 May 2012 02:54:38 -0700

Final-Recipient: rfc822;################@##############
Action: failed
Status: 5.5.0
Diagnostic-Code: smtp;550 relaying mail to ################# is not allowed

--9B095B5ADSN=_01CD299C0888E07C001CA7A1blu0?omc3?s1.blu
Content-Type: message/rfc822

Received: from BLU161-W65 ([65.55.116.73]) by blu0-omc3-s1.blu0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675);
     Wed, 23 May 2012 02:54:38 -0700
Message-ID: <BLU161-W65FD10B04571B7C1A97B7EB6030@phx.gbl>
Return-Path: robforrest123@hotmail.co.uk
Content-Type: multipart/alternative;
    boundary="_517b36bc-f50e-4056-81ff-c55f93271170_"
X-Originating-IP: [82.33.204.39]
From: R F <robforrest123@hotmail.co.uk>
To: <##############@###############>
Subject: Testing ############## emails
Date: Wed, 23 May 2012 10:54:37 +0100
Importance: Normal
MIME-Version: 1.0
X-OriginalArrivalTime: 23 May 2012 09:54:38.0360 (UTC) FILETIME=[11037180:01CD38CA]

--_517b36bc-f50e-4056-81ff-c55f93271170_
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

....