This can be done easily.
1) Add non user visible checkbox "valid"
2) Make a plugin that set this false when user is modified in the front end and true when user is modified in the backend
3) Add this as criteria for all your userlists
Additionally, you may make the plugin to mail admin a notification.
If you do not want to hide profiles that are not validatad, you need to make a bit more programming. This would be a day or two worth of work if implemented as a plugin.
-Mikko