Been running my mail server on Linode for almost 2 years now. Fortunately I've yet to run in any issues. Having setup all the stuff properly from day 1 probably helps (TLS, SPF, DKIM, DMARC, MTA-STS).
Did the outgoing emails for the site ramp up fast? Did you only encounter issues with Gmail or with other big providers too?