A few days ago I googled around for trust centers offering personal e-mail certificates. Giving up after searching a half hour, because all of them (VeriSign, trustcenter.de, ...) require a fee.

Today I found my account information coincidental in my registration documents with Thawte: I already was in the possession of certificates! However these were already run off and only for no longer valid email addresses. So I renewed my certs and I'm really able to send signed mails: Outlook 2003 handles all that nicely while the older versions had some problems there. And best of the story: nothing to pay for! Now I only need some notaries to get my identity trusted.