I had exactly the same experience. For context I run a SaaS targetting small/medium businesses, who usually have in-house email servers with extremely restrictive spam filters. The IP was on a blacklist, so some of my customers just couldn't use my service. I contacted SendGrid and their only solution was to upgrade from a $20/mo plan to a $80/mo plan with a dedicated IP - they wouldn't even move me to another IP in the pool.
Given this, and my volumes of mail were increasing (once you go over 100k emails/mo SendGrid's pricing goes up a lot), I setup my own mail server using Cuttlefish [0]. I set it up on an OVH instance that I pay £2.50/mo for. I contacted them to enquire about spam policies before opening an account, and they said they take it very seriously and monitor outgoing SMTP for spam.
The IP address I ended up with was still on one blacklist, but the process to remove it was pretty easy (fill out a form, and explain the situation) and took about 1 day. I set this up around 6 months ago and have had no problems with deliverability since then, I'm now up to sending around 300k emails per month.
Unless you are doing a TON of sending, you are better off with a shared ip since it will have a known reputation. That is assuming that the provider is maintaining the integrity of those allowed to send with that ip. I haven't used sendgrid, but mailgun has been good about moving me off of any ip I don't like. Although I wish they were more proactive about it, I have setup a weekly monitoring script to check a bunch of the blacklists. If there are any issues, I will have them move me. And I am still on the free tier so I can't complain.
I've been doing this for 6 months now, and haven't had any issues. Over the last 7 days my deliverability of 64k emails has been 99.5%. The only bounces I have are because of invalid email addresses or mailboxes being full. I didn't do any 'warming up' of the IP when started, I just started sending.
I've heard this many times, and maybe it was true before but it doesn't seem to be any more. I suspect now companies like Sendgrid still spread this FUD so people are more willing to buy their services and assume it's the only option.
I'm curious to know what type of customer you have? My customer base is made up of quite a few less tech-savvy types and we get a lot of issues with spam for AOL and MSN accounts.
And I don't show any bounces either. Stuff getting sent to spam doesn't give you a bounce message usually. It will appear to have been delivered successfully.
As for needing to warm up the IP, I think there is still something to that. I am surprised you were able to just start right off sending large volume. My guess would be that that you lucked out and got a gently used IP address by chance. The fact that it was on a blacklist would indicate that it probably was previously used rather heavily... just enough to get blacklisted at one place. But not abused in a way that got it blacklisted other places.
Given this, and my volumes of mail were increasing (once you go over 100k emails/mo SendGrid's pricing goes up a lot), I setup my own mail server using Cuttlefish [0]. I set it up on an OVH instance that I pay £2.50/mo for. I contacted them to enquire about spam policies before opening an account, and they said they take it very seriously and monitor outgoing SMTP for spam.
The IP address I ended up with was still on one blacklist, but the process to remove it was pretty easy (fill out a form, and explain the situation) and took about 1 day. I set this up around 6 months ago and have had no problems with deliverability since then, I'm now up to sending around 300k emails per month.
[0] https://github.com/basho/cuttlefish