We would like to setup two servers with pihole behind a load balancer for failover/capacity/redundancy. One sticking point we have is the IP address that is cached on the downstream DNS client. If one of the pihole servers goes down, the clients would see a "Could not be found" message instead of …

Check your /etc/pihole/gravity.list. The correct IP should be there. If so, then it should work. Maybe you have to wait for the DNS cache to time out on your clients?