I've run my own mail servers for many decades and have never had any deliverability issues. I've also never used bargain basement cloud VPS services with horrible reputations.
The best way to ensure a good reputation is to obtain your own address space from a RIR. Barring that, you need to choose a provider with a decent reputation to delegate the space to you.
The best way to ensure a good reputation is to obtain your own address space from a RIR. Barring that, you need to choose a provider with a decent reputation to delegate the space to you.