Well this is certainly a problem, but it's mostly limited to the first login, as (IMHO) the mail server(s) should use DKIM so greylisting can safely assume it's

Well this is certainly a problem, but it's mostly limited to the first login, as (IMHO) the mail server(s) should use DKIM so greylisting can safely assume it's receiving mail from the same (legitimate) domain (the actual IP used becomes irrelevant). The first password-less login email could allow for a longer expiration, and it wouldn't be worse than a password-ful first login with email verification anyway.