I have a Fortigate 100D with 2x BT Business Infinity Fibre connections acting as WAN1 & WAN2.
The BT lines come with 5 static public IPs each and I have my DNS hosted through CloudFlare pointing at a static IP on one of WAN connections.
(Say you do a nslookup on mylesgray.com you will see 217.45.201.1 as the public IP).
We want redundancy for our A Records (for hosted websites, VPNs, ssh etc) but obviously the 2x BT lines have 2x different sets of public IPs, so if WAN1 goes down, we are dead in the water - no failover as the address is static.
I had looked up external DNS failover but that seems messy and very wrong to me (round robin annoys me). Then anycast came up as an option, however, Anycast seems to require and entire /24 block or in some ISP's casts even /22. We are running an enterprise level router so using BGP etc is not a problem.
Can anyone shed any light on how to achieve failover for DNS A-Records short of buying a /22 block of IPs or using Round Robin DNS?
Just a couple of notes: Anycast doesn't really provide A record failover. You mention "external DNS failover" and roundrobin - these are not the same things at all. Roundrobin is having multiple A records for the same hostname. DNS failover is changing a single A record to a different IP address when a link goes down and, ideally, changing it back when the link comes back up.
As Lukas mentions, DNS failover is generally not the greatest way do this for the reasons he mentions. It does work for most users but there is a delay from caching and DNS servers that disregard TTL's that will impact time to failover to the alternate IP address.
Should you wish to continue down this road, there are various 3rd party DNS services (DNSMadeEasy, Amazon Route 53, many others) that provide this service. Some of the various link balancers (PepLink, Baraccuda) can also do a variation of DNS failover if they are acting as your DNS server. Depending on your environment, it's also possible that you could also write a custom script that checks the status of your links and updates IP addresses as necessary.
BGP would not provide you any relief unless you own and manage your own ASN and IP address block. The ideal solution would be to apply to your local Regional Internet Registries (RIPE/ARIN/etc) for your own IP block and ASN and run your own routers to advertise the route out of the appropriate link.
Doing Failover with DNS records is considered bad practice by quite some admins, because:
DNS records have a Time To Live which you have to balance between performance (high TTL = long caching) and update behaviour (low TTL = changes propagate faster).
Some DNS clients and recursive servers (like ISP's ones) tend to ignore TTL values completely or set their own.
AFAIK, CF's minimum TTL is 5 minutes (on free accounts, at least).
I'm not working with BT services myself but could there be an option to move IP addresses between the two uplinks? I'm not sure how this can be done with your setup, though.
As you're not afraid of running BGP, you should instead talk to BT to see if you can announce your public IP addresses to them with BGP, thus enabling dynamic routing between internet and your router. Your server would have only 1 IP, routed through one or another pipe.
As such, there won't be any need of a public AS or even a /24, as you would be using BT IP space which will be aggregated in their network.
However they might support the BGP option with their "Business Infinity" offer, so you could also take a look at BT's leased-lines, to upgrade your existing links.
They do offer BGP4 amongst their "resilience" package. However cost might not be the same as "Business Infinity".