Have you checked the logs to see what's happening? Any addons that touch email settings or user validation?
Ours is working fine... if the email bounces, it gets marked as invalid or if the user changes their email, it's invalid until they confirm the new message. We're on the latest 1.5.x revision (.18) with no issue like this.