The problem with public keys is that it moves the centralization out toward discoverability rather than the actual name store. This is why something like a global source of truth like the bitcoin blockchain actually offers some technical advantages here.

Ultimately a Bitcoin L2 protocol that hashes current namespace to a Merkle tree on the Bitcoin blockchain would certainly work nicely. The question then becomes, how does this protocol work? Can we make it work without a federation?

Imagine a network that uses proof of work to find solutions for global names. These miners (or name finders) could just spend their time searching for solutions for names. When they find a solution for a name, they publish it to the Bitcoin blockchain. They could do this on demand, or use free time to search for solutions to common names/words.

Of course, this ties the economics to Bitcoin. Finding a name must be at least as expensive as publishing a transaction, but the benefit to the miner would actually need to be more than the benefits of mining Bitcoin with the same time.

The difficulty for finding a name solution could be tied to the current Bitcoin difficulty, but also to the entropy of a chosen name (using some common algorithm). Less entropy -> higher difficulty

There's a lot to think on there, and I am just spitballing, of course.