use Net::DNS;
my $resolver = Net::DNS::Resolver->new;
my $domain = "perlmonks.org";
my $query = $resolver->query($domain,"MX");
if ($query) {
    # They have an MX record, send the mail.
} elsif (gethostbyname($domain)) {
    # No MX record, but the host exists.  Send the
    # mail.
} else {
    # No host, and no MX.  No mail for you!
}