Real hardware servers are not required to host email.
I agree, and said that in my parent comment.
A new VPS provider may work well and make you happy, but later on, many spammers may start abusing it to send spam. Then, major email providers begin to block the entire IP subnets that belong to your VPS provider and you are screwed.
Since spammers typically can't afford to buy and house servers, having your own physical or dedicated server will likely increase the likelihood of everything being fine for a long time or forever.
One example of a good signal: if you cannot sign up online, but must make personal contact with the provider (via email or other means) to set up a server. It's a minor inconvenience for you — you're only going to do it once — but spammers expect to have to do it many times and won't bother.
The point is not that much that there are such blocking lists, the point is why admins use them. Surely that's blocking a good chunk of spam, but also legit sites.
1: "As you should know now: It is not you, it is your complete provider which got [redacted] listed."
FWIW, I've been using Hetzner for the last 10 years or so (but bare metal server, not a VPS) and haven't had issues.
My recommendation is to use a provider that doesn't host spammers. Hetzner is not great at that in my experience, but sounds like they've been fine for you. Smaller providers who know their customers and are able to pay attention to how their network is being used are generally quite good at making things difficult enough for spammers that they go elsewhere.
This is a key difference. Many people who have a bad time self-hosting mail set up with a minimum-effort major provider like Hetzner or DO — you're guaranteed to have spammers as neighbours some of the time, and other networks will behave accordingly when deciding whether to accept your mail.
A real server in a proper datacentre is great — I do the same — but as a lower-cost option a virtual server with a small, clueful provider who knows their customers also works just as well.