Ask HN: Email provider for sending transactional emails?

I run a website monitoring service, and send out email notifications to my customers whenever there is a problem. I'm currently using SendGrid with a shared IP, however a lot of my emails are being rejected due to blacklisted IPs. As the notifications don't get through, it leads to not very happy customers.

Over the past month I've sent 75k emails, and nearly 5,000 have been blocked due to the IP being on spam lists (I should note that 0 of my emails have been marked as spam). My customers are usually small businesses who have overly aggressive spam filters, so that definitely doesn't help.

I contacted SendGrid support and the only thing they could recommend was that I upgrade to a plan with a dedicated IP. Although $19.95 to $79.95 per month isn't too bad, after you send 100k messages per month their prices go up quite a lot (it jumps to $165 for 200k messages), so I've been thinking of moving anyway. The only thing I use them for is as a SMTP server - I don't use any of their marketing tools.

So.. can anyone recommend a good provider who will be more supporting?