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.
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.
https://cuttlefish.io https://github.com/mlandauer/cuttlefish
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