I kind of like this idea. It could also be a way to deliberately burn an account if you want to get rid of it.

How about such a service also sending out notices which provably came from that service after it has access to a given key? That is, sign something in a way that requires both the service's private key and the leaked private key.