How much of this is just down to your mail server being randomly assigned an IP address with dubious history or not?

Hard to tell. My server's IP was not on any public blacklists (confirmed by https://multirbl.valli.org/) and it was whitelisted on DNSWL.org at medium trust level.