This is where user group promotions come in handy. Rough steps:
Change the permissions of the "Registered" user group to be as restrictive as possible (setting permissions to "No", don't use "Never")
Create a new user group, e.g. "Verified users" (or similar)
Give that user group any permissions that you took away from the "Registered" user group
Go to "Groups & permissions" then "User group promotions" and then "Add promotion"
Under "Add user to groups" select "Verified users" then on the "Apply this promotion while..." tab select the criteria that needs to match, e.g. the "Verified users" might be users who have posted at least 5 messages, and registered at least 1 day etc.
And that should do it. All of your existing users who meet the criteria will be promoted to the "Verified users" group when they next log in or within an hour (or you can just run the promotion process manually under "Tools" and "Rebuild caches".