Does anybody know where I could find a list of the criteria that would make a lead's email become invalid?
Have a look here - lots of useful info (including the comments section): Monitoring Email Deliverability: Bounces - Part I
The only system requirement for a lead becoming Email Invalid is if the lead is bounced as invalid by the receiving server. Specifically, if the bounce category on the lead is Category 2. You can see the bounce category on the lead by double-clicking on the Email Bounce activity in the lead Activity History and viewing the Activity Details. One of the details will be the bounce category with a numeric value. Category 1 is a spam bounce and Category 2 is a bounce due to invalid email address.