Hosting DKIM records on a separate nameservers

Solution 1:

RFC 4871 addresses some concerns for subdomains that are not admistratively related to their parent, I.e. the operator of .com taking control of the example.com DKIM records and that with normal DNS delegations there is no guarantee where the cut of administrative control is (i.e. with vanity TLD domains such as .walmart compared to walmart.co.uk there is two levels of difference where administrative control starts and that can even become deeper).
The RFC considers that an acceptable risk for the same reason that it is acceptable for normal domain delegation.

Therefore as far as I can tell subdomain delegation for a _domainkey. subdomain is not outright forbidden and such DNS delegation ought to be followed but §8.13 also says:

Note that a verifier MAY ignore signatures that come from an unlikely domain ...

Solution 2:

There is nothing in the RFC that would indicate that all records must have the same nameservers. However, in section 8.4 it is recommended that strict validation of glue records be applied. It is possible your server is not supplying the glue records.

It is common to setup sub-domains as separate zones. These can be served by the same server or delegated to different nameservers. example.com. is a sub-domain of the com. domain.

Having _domainkey as a separate zone makes updating the sub-domain simpler as only that zone needs to be reloaded. When rotating keys, only a few entries need to reloaded. It also prevents accidental changes to other records in the domain.

I haven't tested, but it may make sharing the zone among multiple domain simpler. I'll be testing this soon for my _domainkey and _dmarc sub-domains.