You seem to be focused on a technical solution when in fact you face a largely psychological problem.

There are a number of reason a user might enter an invalid address:

Desire to avoid 'spam'
Typos
Hacking your system

Of these the hacking issue can be dealt with by checking the email address for such things as shell characters and excessive length (buffer overflows). You have been referred to appropriate source of info for this. 

Typos are impossible to differentiate from fake addresses unless you insist that users do the old password repeat. But even if a valid email is entered what does that mean? I have a garbage email address that is certainly valid but is never read and automatically cleared. You can have that but, valid or not, it is little use to you. I was forced to do this after my automated website submission script generated 400 reply emails in the first 20 minutes and over 1000 for the first day. My original address still receives over 30 spam messages a day from this one judgement error!

So to the psychological bit. Let's be frank. You generally want valid email addresses for marketing purposes. One man's marketing is another man's spam. Nonetheless you can be confident that if a user is willing to take the time to type in their name and email in return for some sort of enticement they will *probably* accept some form of validation.

To put it in marketing speak you must get them while they are hot. The best way to validate an email address is thus to immediately send an email to that user via auto responder. To get their widget, read the secret files or whatever they have to respond to this email in some way. If they respond you *have* validated them, at least for that single moment in time - they may killfile your address or remove that username, redirect ... but you can't win them all.

There are many ways to get the user to respond. These can be quite subtle and unobtrusive if you put your mind to it.

The blank email reply
The subscribe me in the subject or body reply
The link to the secret pages
The link to a cgi
The password
The cookie via html/javascript or perl or whatever

Just a few comments on your script.

A huge security hole seems to be that you perform absolutely *no* character checking on $domain. Any user input, especially input that may be passed to a shell needs to be validated and have shell chars removed. See validating an email address, perlsec and taint or -T

The second issue is that the existence of a domain proves.....that the domain exists. As I read it your script will validate mickey_mouse&donald_duck@hotmail.com. Whilst this may indeed be a valid email address it is certainly not my valid email address.

return 1 if (! $user ) or ( $user eq '' );     # No user!
return 2 if (! $domain ) or ( $domain eq '' ); # No domain!

# The second part of these lines is *never* looked at. If $user =''
# then !$user is true and they return without ever evaluating the 
# bit past the or. You don't need the parents either.

return 1 if ! $user ;  # No user!
return 2 if ! $domain; # No domain!

# The if ! (if-not) syntax is what unless was invented for

return 1 unless $user;   # No user!
return 2 unless $domain; # No domain!
[download]

Hope this helps.

tachyon