I'm not persuaded by appeals to what DNS was or wasn't built for (unfortunately neither is the IETF; to wit: DNSSEC). I agree with you that the ask here is big! But I'm not convinced there isn't a cleaner solution that works within our constraints.
To start with, first implement (1).
Assuming .internal points to internal-only IPs, and you are reusing internal IPs (each customer VPC can have arbitrary private IPs), you can have ni-172-16-0-5.customer.internal.somedomain.io return A record to "172.16.0.5". (You don't have to add .customer, but you might gain some useful analytics)
A customer needing a hostname for 172.16.0.5 can resolve ni-172-16-0-5.customer.internal.somedomain.io. By default it'll use whatever DNS server/resolver they have configured (or yours with option (2)). The request goes through public DNS until it gets back to somedomain.io (your domain) and you return the result.
Upside: You're not hosting all the customer's DNS resolution. Downside: The customer will see a longer round-trip for .internal requests, and their VPC needs a NAT gateway.
Next implement (3).
Intercept all DNS traffic that matches ".internal.somedomain.io" and spoof responses. Write this tight enough that it will only return responses when you are sure they won't break clients, and pass the rest to the public DNS using option (1), which prevents from having to mess with TCP connections (they'll be slower though the public internet, but it's TCP, what did they expect?).
Upside: You are only returning results for .internal, everything else can use somebody else's DNS, and the customer doesn't need a NAT gateway. Downside: Requires custom engineering which is subtly complex, and is hidden magic the customer doesn't expect, so could cause troubleshooting headaches.
Next, implement (2) as an opt-in.
Have your VPC DHCP server return your internal dns server. You resolve .internal locally and handle the rest as a big hulking resolver. You can also slip this DNS server into their containers, but as a customer I'd want a giant red flag in the docs that advertises this.
Upside: Works in every customer scenario. Bonus: now you can return reverse records. Downside: Now you really are hosting the customer's DNS resolver.
1. Use ".internal.someotherdomain.io" and the regular old public DNS. (this probably only does half of what you want)
2. Use dnsmasq at the edge of each .internal subnet, and maybe require the customer to configure your DNS in their container. (I believe this is what AWS does?)
3. Intercept tcp/udp port 53 at the subnet edge, spoof your own responses for .internal, pass through anything else to wherever it's going. Dealing with tcp could be tricky, udp is easy. Probably this will break some clients, and generally be the hardest thing to implement.
I think the best option is #2, as it will actually work reliably and with the least difficulty for everyone.