The protocol mechanism actually creates the origins they look like, which can result in persistent storage being used across the browser: cookies, localStorage, IndexedDB, etc. It's necessary/appropriate to clean up this storage when the extension that created the protocol is uninstalled as nothing else will. The primary rationale is privacy, but it's also good to not waste the user's disk-space.
Currently, WebExtensions clear the storage of the moz-extension origin for the WebExtension at https://searchfox.org/mozilla-central/rev/0b8ed772d24605d7cb44c1af6d59e4ca023bd5f5/toolkit/components/extensions/Extension.jsm#237. You can see the call to
clearStoragesForPrincipal on nsIQuotaManager which wipes out all storage for the extension itself, plus a separate call to wipe the overloaded use of userContextId for the "storage.local" backend (which is not directly visible to the extension). This or something is an appropriate place to wipe the registered protocol origins.
I thought QuotaManager had a way to perform this clearing already, but it turns out I was wrong. https://bugzilla.mozilla.org/show_bug.cgi?id=1493002 now tracks making this clearing possible.
Note that for cases where there's a reason to keep the storage around, the WebExtensions logic already supports a "extensions.webextensions.keepStorageOnUninstall" preference which leaves a WebExtension's storage around. This is really only appropriate for extension development profiles temporarily loading extensions over and over via about:debugging, however. It shouldn't be used as a mechanism to allow users to persist data... at that point I think real UX is needed.