We reported it to SendGrid and their only option was to upgrade to their $89.95 plan to get a dedicated IP. That plan comes with 100K monthly sends and we are nowhere near that.
So, the choice was to have a significant portion of important transactional emails, like registration, not go through or overpay for a plan that is wildly overmatched for us.
Email is hard, but this borders on unethical. Customers pay for and integrate a service that simply doesn't work as advertised. They make no offer to mitigate (e.g. change to a new shared IP). It's just "oh yeah, if you want the service to actually work reliably, you need to pay us 6X more".