Maybe do a test with Sendgrid or Mailjet to see if they have more success? Generally Gmail hates small email providers... and Google doesn't care about anyone but its advertisers.
Don't rely only on mail for booking confirmations?
You need an alternative way for users to get their confirmations, and any associated documents, simple as that.
Those materials can be provided in a self-serve download area.
Moar IPs. Spread your load over after warming up the new one.
How to Stop Gmail Rate-Limiting
I don't have a good answer for stopping it given what you have tried thus far, but one can reduce the impact by distributing the outbound SMTP to different SNAT's, CIDR blocks, data-centers or even AS Numbers depending on how complicated of a setup one is willing to support. Every SNAT of course needs FCrDNS and all the additional CIDR blocks would need to be included in your existing SPF but that should reduce the threshold in effect.