This could be because the email address is being (accidentally) marked as verified by a link-scanning service before the user gets to the message. That’s the case we were running into, particularly with Microsoft-based email addresses (@live.com, @hotmail.com, @outlook.com)
You may want to look at this post, which includes instructions on how to enable a new feature that should prevent or reduce the “robot used my verification link and now I get an error” scenario. 