Probably your server's IP or name is listed on a blacklist. For the delivery of your emails you must necessarily check if your server is listed on a public eMail server-blacklist. 

How do I proceed with a freemail-provider?

The best thing to do is to check the mail-logfiles on your server, if each eMail has been delivered to the receiver for sure.
If yes, you have to contact the mail server operator and ask him, why the eMail didn't arrive.

Alternatively, setting up an extra eMail account for a domain managed by you is worthwhile.

So you have directl access to the anti-spam settings and you are not depending on the eMail provider.

How do I proceed with a server-operator?

The best thing to do is to check the mail-logfiles on your server, if each eMail has been delivered to the receiver for sure.
If yes, you have to contact the mail server operator and ask him, why the eMail didn't arrive.

In case you are blacklisted ask them to get a whitelist record if possible.