Originally it was thought that Hotmail had been added to a RBL that DCU's Computer Services Department was using.
... After further investigation it appears that it is an issue with Redbrick using different MX hosts for IPv4 and IPv6 email traffic:
rfc 974 states:
If the list of MX RRs is not empty, the mailer should try to deliver
the message to the MXs in order (lowest preference value tried
first). The mailer is required to attempt delivery to the lowest
valued MX. Implementors are encouraged to write mailers so that they
try the MXs in order until one of the MXs accepts the message, or all
the MXs have been tried. A somewhat less demanding system, in which
a fixed number of MXs is tried, is also reasonable. Note that
multiple MXs may have the same preference value. In this case, all
MXs at with a given value must be tried before any of a higher value
are tried. In addition, in the special case in which there are
several MXs with the lowest preference value, all of them should be
tried before a message is deemed undeliverable.
It looks like Hotmail are only trying a fixed number of MX records (either 1 or 2) and then giving up on delivery (the ipv6 hosts don't have IPv4 addresses and it looks like Hotmail doesn't use IPv6 yet). Since the two lowest preference servers are IPv6 only addresses delivery fails.
I (redgiant) have raised the issue with Hotmail support and the Hotmail product team (15 dec 2004).
Hotmail never got back to me about this issue. I gave up chasing it... If you know someone on the Hotmail team - bug them about it. ;)