Hmm... I see that this couldn't be implemented for all proofs (e.g. it's not easily possible to identify proof document given user's github handle as we'd have to browse through all gists).
But a limited version that you also outlined: WKD/HKP lookup by e-mail? Why not! keys.openpgp.org has e-mail based lookup too.
For some providers like Mastodon it's also possible as the proof document is in the profile.
For the record Keybase had its own database of all proofs so they could easily query for "give me all proofs for someone that's X on GitHub". Currently Keyoxide operates in a "stateless" mode and this makes it quite a lot easier (and there are no GDPR questions and the like).