sendmail mfl. fixar detta lätt, iaf att verifiera om det bakom @-tecknet är en valid emailadress som existerar. (Den kollar upp att det finns en mailserver och jag tror tom den provar kontakta den för att se om den är uppe.)
(Precis som du säger via MX records om de finns..)
Det framför adressen är knepigare men vissa mailservar svarar fortfarande på kommandot VRFY.
Det är ju bara att telnetta till mailporten och köra VRFY <adress> för att prova.
Jag tror nog att de flesta som skickar spam kollar upp åtminstone det efter @ tecknet innan de mailar.