I wonder though if it wouldn't be more practical to support the Web Key Directory protocol [0]. WKD is both more secure than HKP (as it's always over HTTPS and authenticates user's domain), it's enabled by default in a growing number of email clients (Enigmail, GPG for Outlook, KMail) and providers (kernel.org [1], posteo.de), it's used by GPG when locating a key and the setup is incredibly easy (just put binary key in one location).
(to check it out try `gpg --locate-key torvalds@kernel.org` in modern GnuPG)
From my perspective it looks like a perfect match for ProtonMail for both use cases: exposing @protonmail.ch users' keys and fetching keys of contacts on other servers.