Release a new API that uses symmetric encryption instead of a one way hash. Use however many rounds are necessary to prevent brute force attacks. Gravatar keeps a list of generated keys, but not who generated them. The API accepts a key ID and encrypted email. That makes the keys convenient to generate and change. Deprecate the old API and turn it off some day.

I think that works, but I try not to think about crypto at three in the morning, or at all really.

EDIT: Also, a consumer site could implement this themselves with a simple proxy server. They could even open up the service to other sites.