Apparently it's from 1901 (Murray code) or 1932 (ITA2).
The fact that both Apple's and CP/M codes came out roughly at the same time, both on microcomputers, shows that it was probably just a design decision.
You could start the encoding with two bytes, so that if the most significant bit of the first byte is 0, the length is that byte plus another. That gives you 32KiB strings with just a byte more. Short strings might suffer, but I think the overhead is reasonable.
The next level (110x xxxx) would give you 8MiB strings, which are going to be fine for most things.
And which modern C compiler fits into 64KB? Even TCC needs 100KB. But that's beside the point. No machine of the last 36 (I'll push my chances, 40) years needs to fit a compiler in 64KB.
I also started going down this rabbit hole when I wanted my homelab to just work in any device, and for advanced use cases Let's Encrypt isn't enough. I tried long and hard to get a sub-CA certificate, but apparently that's in the realm of «if you need to ask, you can't afford it».
And if they don't, DNS is already a database. You could just query domains to check their certificates. People running recursive DNS servers could double-check certificates.
> every government will absolutely double-issue certificates to police, secret service and friends of goverment, and no one will have any recourse.
Countries already have CA that issue certificates with more legal force than a handwritten signature. I can open a bank account, pay my taxes and sign up to all government services. But I can't use them for a webpage.
> With DANE (or other country-issued certificates)
DANE isn't a country-issued certificate. It's a scheme where you store your public keys on DNS records. Of course, now we have the issue that DNSSEC (signed DNS records) isn't widespread and the whole issue with DNS registries.
It's funny to see that the issues with X.509 certificates, are being solved by what X.509 was intended to be used for: a directory system. It's DNS instead of X.500, but it's a start.
The fact that both Apple's and CP/M codes came out roughly at the same time, both on microcomputers, shows that it was probably just a design decision.