I'm not sure how relevant this is, but I recently received this error message after trying to email an xtra user (email addrss has been changed, obviously):
This message was created automatically by mail delivery software.
A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:
all hosts for 'xtra.co.nz' have been failing for a long time (and retry time not reached)
I re-sent the message today and it seems to have been sent OK this time.