I just started testing out the email verification feature for new leads, and it seems the system isn't a big fan of the + symbol being used in an email (which I commonly use to test the same email address for different things).
When I ran the same email through other online email verification tools they came back acknowledging the email address WITH a + sign was valid, but the HL automation execution log is coming back with an error of "Unable to send e-mail, contact's e-mail is invalid"
And when I go into the contact to manually change / check the email, any change that includes a " + " before I re-verify comes back with "This email is marked as Invalid as smtp_error"
I know many Gmail (especially) users tend to use the + sign for tracking where they submit their email... this causes a lot of valid leads to be rejected