The one true solution is client authenticated TLS. For the life of me I can't understand why 25 years later certificate management is still such a mess.
We don't need some perfect universally recognized root trust system to get started. Why doesn't the sign up process for authenticated API access routinely include the issuance of a certificate signed by the API owner?
Unlike for interactive users there's no expectation that a customer will be accessing an API from some random computer where he might not have access to his certificate store.
I agree it's awful to use, but what I don't understand is why no one has bothered to improve the tools.
It's one of those areas where the underlying tool (either a library like openssl or NSS, or an OS feature like SSPI) could do the hard work in one place and make it simple for downstream libraries to wrap the functionality.
In other, somewhat analogous, domains that happened, but for whatever reason not in this case.