Additionally: the basic problem of routing DNS requests based on domains is trivial. It's probably less than 100 lines of Rust to send `.internal` to our servers and anything else to a public recursor. But the goal is to get our own code out of the path of people's DNS lookups, even if it's just 100 lines of Rust.
So running dnsmasq or some systemd resolver server thingy doesn't really solve anything for us. Before we did that, we'd just make our `init` a DNS server. But it'd be neat to come up with a way to to solve the problem without having a SPOF server dependency. It might could be possible! You can already see that if you assume a specific libc, you can just preload a libc stub resolver that routes requests. But, of course, we can't assume a particular libc.
Most of my point here is just that "standard" Linux DNS is bad.
It -is- possible, as others have commented, to do this within the VM or container but they need a way to get that information. systemd-resolved does this. From what I understand of fly.io, the container is setup by the user, so you're not going to have control over their networking configuration or environment - is that right?
Now there is an alternative, which is instead of using .internal, to use a public facing internet hosting that is delegated to your internal DNS servers. That way they use their normal DNS, and it resolves to your nameserver. But the DNS needs to be public, and critically, if the internet DNS goes down, your .internal resolution will also stop working. Which is highly likely to cause problems for peoples applications. And also adds un-predictable latency to their local service connections which is almost certainly going to cause problems - it's not a good idea.
Having said all of that, generally speaking, it makes sense that -you- provide the DNS. It's pretty much the standard way that your 'ISP', 'Hosting Provider', etc, provides the DNS rather than relying on the public internet DNS. Only a few years ago there was no such public DNS.
The other possible alternative would be to leverage multicast DNS (libnss-mdns/avahi-daemon) or LLMNR but I'm not sure those are really ideal for this use case either. And in both cases requires resolver support that you dont get from the basic glibc resolver. So for your use case, may still not be workable.
So I think you're stuck, unless you can mandate that all of your VM images use systemd-resolved and somehow communicate the config into them.