This would only work if you could achieve this search with the use of a zero-knowledge proof. Actually disclosing your password to the service would defeat the point.
Yes, this is a weakness. The password would need to be disclosed in the form of a hash of the password, and the hash algorithm has to match what everyone else does.
If the service and your site were both compromised, then it would be possible to match up incoming hashed passwords to users by timestamp. But even so, the fact that no passwords were reused will hopefully make cracking the hashes harder.
