Found today CAcert, an australian non-profit association, which issues SSL certificate for free. As I had to renew our (selfsigned) certificates anyway, I took the few steps needed to let them sign by them. Now, all our certificates (for http, imap/pop and smtp) are valid again and not only selfsigned
anymore.
If you want to get the Root Certificate into your browser to avoid the annoying warnings, go to cacert.org/index.php and import their root certificate. They even have a bug in bugzilla.mozilla.org to ship the root
certificate with Mozilla by default.