It's actually not that difficult, at least the vb part. Like I said, create a plugin using hook location register_addmember_process (just go to Plugins & Products > Add New Product). For the code, it would be something like:
Code:
if ( /* check if $vbulletin->GPC['email'] is not in other database */)
{
$userdata->error('email_not_in_other_database');
}
Then you'd need to go to Languages & Phrases > Phrase Manager and press the "Add New Phrase" button at the bottom. Choose Phrase Type "Error Messages" and enter varname email_not_in_other_database, and put in whatever message you want.
But like I mentioned before, I don't know how to tell you to do the " check if $vbulletin->GPC['email'] is not in other database" without more info. If you know how to do that part, then you're there.