I made similar experiences with a Hetzner VPS that I use to run mailcow (the TLD I'm using is .xyz). I refuse to give up though. One time I tried to contact my local city authority but they straight up blocked my emails. What followed was an email exchange with a slightly annoyed undertone by the guy that I reached via the postmaster address. In the end he apparently put me on some whitelist and my mail could be delivered.

Especially annoying is that in some cases filters blocking my mail are used on the postmaster address too, so to resolve an issue I have to use my gmail address.