Just wanted to chime in here. I too was having issues with Sendgrid with some of my domains - icloud.com, me.com, live.com, hotmail.com, yahoo.com as well as CRM’s like Zoho - all blocked.
Then I hopped onto a client’s Sendgrid account that setup sender authentication recently - they send 1000’s of emails per week. Not a single suppression from any of these domains in the logs since.
p.s. Postmark looks good but if you’re only jumping ship for this particular issue, then just setup sender authentication.