Interesting. There was a project nearly identical to this on one of the freelance boards I use to pick up jobs. I didn't bid on it because the poster specifically stated that automated routines would not be allowed - each record had to be checked manually.
I would probably use IO::Socket::Telnet. Something along the lines of this completely untested code:
my $socket = IO::Socket::Telnet->new(
PeerAddr => 'random.server.org',
PeerPort => 25,
Timeout => 3
die "Not an email server\n" if ! $socket;
$socket->recv(my $resp, 4096) or die $!;
die "Not an email server\n" if ! defined $resp || ($resp !~ /^220 / &&
+ $resp !~ /^250 /);
link may be of use in determining other SMTP response codes that indicate it is in fact an SMTP server but not necessarily behaving as you might expect.