I'm in a similar boat. I've moved ISPs a few times throughout the years, and each move it takes a few months to finally get things settled. I'm in the US, and had the best luck for deliverability when I was on a Comcast Business account.
My current ISP, a local fiber provider, was not great getting going. Most of the IPs that they have are in at least 1 spam database, and it took a while for the ISP to reach out to the database maintainers themselves. Even then, since they're a small ISP, the IPs are still blacklisted. The ISP wasn't even a company when the IPs were added to these blacklists.
After a few months they were able to assign me an IP that wasn't in a blacklist somewhere. I still randomly have issues with the big providers though - gmail is probably the most annoying. Like dozzie, my SPF, DKIM, and DMARC setups are all valid.
Overall, I really enjoying running my own mail server. Every now and then there are a few annoyances, but it's worth it in the long run.
