The message I used on the client side contained some SOAP headers. Since this is an untyped message these headers were neither encrypted nor signed. That was a show stopper for me.
I saw this blog post by Nicholas Allen and immediatelly tried the following syntax:
However the request message was still not being encrypted nor signed. I struggled with this issue for some time until I was lucky enough to find Pedro Felix's message in the WCF MSDN forum:
In other words the OutgoingSignatureParts always relates to server outgoing messages while client outgoing stuff is always considered as "incoming". After fixing this the code worked like a charm. I probably should have proactively RTFM myself but at least I felt good for not being the only one who fell for this...