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.