The reason for this seems to be gnupg related: When I start KMail from a terminal and try to send a message, a text ssh-askpass dialogue is shown on the terminal. If I enter my gnupg key password there, the email is being send without any problems.
My assumption is now that ksshaskpass is somewhat broken. ksshaskpass/testing,unstable,now 4:5.8.4-1 amd64 [installed,automatic] --Dennis
signature.asc
Description: This is a digitally signed message part.