For pop emails (no hotmail, no gmail, no yahoo, no aol ...) :
1 - Check RFC email format.
2 - Check if domain exist.
3 - Check MX.
4 - When you send with your "verifed emails", add a % of unverifed email.
For no-pop I have a custom system to clean invalid and spamtraps.
I'm interested in your system to debug emails.