Using MX records for providing mail gateway redundancy

my customer has some Exchange servers and they are using a secure mail gateway from a known vendor for their spam mails. Unfortunately this mail gateway software has developed by SMB-minded people, so it does not have enterprise class features like clustering to provide redundancy. And redundancy is a MUST for the company. Vendor suggested us creating another instance of mail gateway, and in case of failure of primary GW; they are asking us to switch to secondary gateway manually. No way I can suggest this to our customer.

I am thinking about providing some kind of redundancy with MX records. Is it possible to do this kind of configuration with MX records? Or is there anything else we can do to overcome lack of clustering feature on mail GW?

example.com.           1200    IN      MX      10 mailgw1.example.com.
example.com.           1200    IN      MX      20 mailgw2.example.com.
mail1.example.com.     1200    IN      A       172.16.10.1 (mail gw 1 IP)
mail2.example.com.     1200    IN      A       172.16.10.2 (mail GW 2 IP)

(Goal here: if mailgw1: 172.16.10.1 is not reachable, MTA should deliver mail to mailgw2: 172.16.10.2)

Or should I use only one domain and 2 A records for failover? Like this:

example.com.           1200    IN      MX      10 mailgw1.example.com.
mail1.example.com.     1200    IN      A       172.16.10.1 (mail gw 1 IP)
mail1.example.com.     1200    IN      A       172.16.10.2 (mail GW 2 IP)

Reference: MX records, better setup for load balancing and failover