Your DNS records seem good.
This behavior might be caused by the Hotmail DNS cache mechanisms, especially if you tried to send an email from hotmail to that particular domain before your new MX records were active.
Better try sending another email from Hotmail after 24 hours and I think your issue would be gone.
Meanwhile in about 24 hours after sending your unsuccessful Hotmail messages you should have reports back to your Hotmail account explaining why these messages failed receiving the destination.