Good way to handle host key checking on multiple networks?

Implement IPv6. Add globally unique addressees to hosts, and to DNS. Which network becomes obvious by /64 subnets.

A big project just for your administrative convenience, maybe. But it may become a bigger problem if an organization ever merges or restructures or uses VPNs, introducing address conflicts.