[currere]

Couldn't the service allow you to check your private keys, rather than check a public key, without transmitting the actual key.

You know (pub,priv). They know either (pub,priv) or (pub).

Essentially, make use of your unique (probably!) ability to sign something with your private key.

There's the issue of traffic analysis which needs to be solved - they have to reveal to you whether the key is compromised, and there's only two possible answers, so they have to be careful not to reveal it to in the traffic metadata.

[currere]

Better yet, they can just publish something encrypted with every compromised public key. Only people with the corresponding private keys can ascertain if they're compromised.