You'll need to try to connect to the domain to see if it exists. So you need a step that happens before you try to send your mail that looks to see if your application can establish aconnection to this resource. See the java.net.* package for a candidate.
This doesn't guarentee success of the mail though. I'm not sure I'd include validation that an email address exists as part of address validation.
Originally posted by Paul Sturrock: I'm not sure I'd include validation that an email address exists as part of address validation.
I wouldn't. Even if you can confirm the domain name is correct, and even if you can confirm there is really an SMTP server working in that domain, it's quite likely that it will refuse to tell you whether a particular address is valid. (That's because spammers use dictionary attacks to harvest valid addresses.)