There are other possibilities too:

1) one of the authoritative DNSes for the domain was answering in the negative

2) that negative answer was cached for period of time TTL

I just tried an email to [log in to unmask]  -- NTF.

/Pete