Hotmail seems to reject e-mail, no apparent reason

[RamonM]

Hi All,

As of late hotmail seems to dislike our qmail mailserver. Rejecting all incoming mail. We are not on any blacklists and we score 100% on mail-tester.com. Furthermore we've instructed our clients to only use webmail in case of emergency and setup a proper e-mail workflow for day-to-day work.

Hi. This is the qmail-send program at server2.8internet.nl.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.

<***@hotmail.com>:
65.54.188.126 does not like recipient.
Remote host said: 550 Requested action not taken: mailbox unavailable
Giving up on 65.54.188.126.

--- Below this line is a copy of the message.

Return-Path: <herhaling@eh***>
Received: (qmail 416 invoked from network); 19 Jan 2014 14:55:28 +0100
Received: from ip91357c44.speed.planet.nl (HELO ?192.168.178.43?) (145.53.124.68)
  by server2.8internet.nl with ESMTPSA (DHE-RSA-AES256-SHA encrypted, authenticated); 19 Jan 2014 14:55:27 +0100
Message-ID: <52DBD95A.3020400@eh***>
Date: Sun, 19 Jan 2014 14:55:38 +0100
From: Ja*** <herhaling@eh***>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: ***@hotmail.com
Subject: geheugensteuntje EHAK 4
Content-Type: multipart/mixed;
 boundary="------------080006010109070403010906"

This is a multi-part message in MIME format.
--------------080006010109070403010906
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit

The "mailbox unavailable" part is misleading. It suggest the mailbox does'nt exist. It does however and our clients have report this exact same response on other valid hotmail adresses.

I'm at wit's end and could really use some support on this issue.