I just did a new FC9 (fully updated) install, and it regularly rejects outgoing mail with the subject error message. The address does resolve, of course, so I'm not sure what it means instead of what it says.
The nameservers in /etc/resolv.conf are the authoritative DNS for the domain, both are up, etc.
Someone have a clue?