intodns.com says: You have reverse (PTR) records for all your IPs, that is a good thing.
I was looking at the config file:
/home/kloxo/httpd/webmail/roundcube/config/config.inc.php
I think it needs to use authenticated SMTP for sending to work.
I have changed the settings to this, and it now works:
$config['smtp_server'] = 'tls://%n';
$config['smtp_port'] = 587;
$config['smtp_user'] = '%u';
$config['smtp_pass'] = '%p';
Server, user and pass were blank before, and the port 25.