> As a consequence, we need to expose critical internal services on the public internet, some of which contain private user data.

No, you just need to have a public DNS entry, no need for that service to be reachable from the internet.

foo.example.com can resolve to your private RFC1918 address, when you send the CSR to a CA, they'll verify your ownership of example.com.