Life could be so easy without MS

> Getting this server off the blacklist was a matter of a one step
> procedure which was resolved within a day.
well then, sharing a link How To Do would be helpful, not?
or do you mean, now I have to register on and/or make a Return
Path certification?

Second google hit:

NB.: The more clear proof you bring to the table, the better.

What will be the impact of free, unobserved email communication, if mail
providers start to use proprietary third party databases for spam
checking? greylisting, isn't a well working solution?

No greylisting does not always cut it, you do need to blacklist certain
IPs from time to time. Some folks use third party lists, which have
problems on their own as you're effectively delegating the decision
about receiving your mail to others, some manage their own list. Point being,
if you send enough mail from your server, chances are this will happen
again and you'll need to work on it no matter who is blocking you.