I don't think it solely relies on providing a signature though. I believe cyrus/theymos looks at each case individually and determines if everything makes sense and the private key hasn't been compromised either. They probably look at when the passwords were changed, and they may even look at personal messages to determine if an account has been compromised through other means.

If it was solely based on signing an address then there would likely not be a huge backlog in accounts waiting to be looked at, and it likely wouldn't be restricted to theymos/cyrus either.  Here's a quote from cyrus:

That being said something like this could be beneficial to those who make common mistakes in formatting their address & signature.