I think that in general, "use solution A to problem X to solve problem Y instead" is, in principle, a valid patent - assuming that it's not obvious that solution A would help with problem Y. After all, patents are about "how do I solve problem Y", not about the general algorithms themselves.

However, the "it's not obvious" part is very important. Not working in the field, it's not at all clear to me if using DNS for data was an obvious idea in ~2000 for building a distributed DB or not.

You are literally describing software engineering.

TXT records were specified an rfc published in 1987. SRV records in feb 2000.

This sounds to me like the web. You make a connection, you request a resource, it returns content and references to further resources that are required to get the full content of the resource you originally requested.