The potential for tracking the IP address of clients requesting keys may already be lessened by using Tor. A new alternative would be for each chatmail server to offer to tunnel TLS (HTTPS) requests of its users to the recipient. It could be constrained to only allow such tiny requests & responses and only towards mail hosts and with rate limits to combat abuse. This is similar to how Signal implemented giphy via their blind proxy: