Hi DerAdi,
I think this is indeed a mail server setting issue, if you use the right smtp settings in the cfmail... I think you just have to ask the provider to give the right permissions and settings.
I also had this problem with not retrieving email while the setting where all good, one time...