My guess is that they have a system that is partially IPv6 ready and they don't know what to do with the reply they get. I remember having read somewehere that it was best to create separate nameservers for IPv6, but I didn't do any more research since then.
Another ISP that had problems is Hurricane Electric, but they are a tunnel broker, so maybe they got confused as well.
It could be a misconfiguration somewhere, but Gmail and lots of other senders were working fine, so it's difficult to try and guess what exactly was the problem.
We also ran lots of DNS reports, all saying that things were fine, showinf us both the A and AAAA record.
All I know is that the fix was as simple as removing the AAAA record, so I thought I would post it here, in case someone notices the same problem and is looking for a solution.
Regarding contacting Hotmail, there doesn't seem to be an easy way. I only found one form that deals with email blocking when sending to hotmail, but we didn't have that problem, we could send to everybody.