How to combine Active Directory with Split-Horizon DNS?

You almost got your solution by yourself.

I'm assuming that srv01.extra.company.com is a server in your own company, so your nameservers are responsible for it.

You are right in that you can't really use stub zones nor conditional forwarders, as the nameserver set up for this purpose will only see the queries originating by your AD DC's.¹

But it's a common misconception that Active Directory must have set the DC's as it's nameservers, or that the clients need to resolve through the DC's.²

In this particular case, you would need to setup a proper BIND that cleanly resolves everything (that includes your AD!). After you have verified proper operation, you would add a zone extra.company.com to this server (effectively masking the real subdomain). In there, you can then override the records to your liking.

Do note however that when this BIND tips over, your whole AD will come to a halt, since all queries by your clients go through this server. So set up accordingly (failover, backup, standby, et al).

¹ Technically, this doesn't hold true for every case: If the client's resolver is capable of following referrals, the authoritative nameserver would see the query originating from the client. However, since almost all OS resolvers are stub resolvers, this doesn't really apply.

² You can safely set even the authoritative NS of your AD to BIND server, but it sure isn't some fire-and-forget solution, it needs some work; for example adding specific records and allowing your DC's to update these. Microsoft has this well documented, refer to this article in Microsoft's Technet for a start. I usually avoid this alltogether, and instead have company.com served by a BIND, and delegate a subdomain ad.company.com to the AD. I don't think it's worth the hassle doing that in a existing AD though, like in your case.

If you want to stick with Windows DNS, the feature that might help you is called Netmask Ordering with Round Robin. When you configure multiple A records for the same host, DNS will return results with priority based on client IP address and subnet. You can define what part of the address mask is used for netmask ordering, and since in your case it is /16, you also need to override default value (which is /24) with

Dnscmd /Config /LocalNetPriorityNetMask 0x0000FFFF

Unfortunately, this will only cover the first two cases from your example, the third one will be tricky since only clients from 10.25.x.x will match the host mask.

If DNS is your only way of doing this, then I think your only real option here is to use BIND views.

AD workstations can point directly to BIND, as long as BIND forwards all requests for your AD domain to the AD DNS servers to resolve. We actually do this in the very large organisation I work for and everything works fine (dynamic updates, etc, included).

What service are these servers running? If they are HTTP you could possibly use something like HTTP redirects to bounce the user to their local server rather than using DNS splitting?