vit,
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:

use IO::Socket::Telnet;
my $socket = IO::Socket::Telnet->new(
    PeerAddr => 'random.server.org',
    PeerPort => 25,
    Timeout  => 3
);
die "Not an email server\n" if ! $socket;
$socket->send("helo mydomain.com");
my $resp;
$socket->recv(my $resp, 4096) or die $!;
die "Not an email server\n" if ! defined $resp || ($resp !~ /^220 / &&
+ $resp !~ /^250 /);
[download]

this 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.