We encountered the same issue and now, after quite some hassle, have a working solution in place, based on the way described in the post from Kilian.
We indeed made a custom java action which has a certificate file and XML-string (generated by the Mendix export to XML) as input, and signs the request with the WSS header elements. It then sends the signed request and has the response of the web service call as output variable. the response can then be mapped with the regular Mendix XML import.
Pity that Mendix doesn't make it possible to easily send a custom request to a published service, but instead always manipulates the request that is being send. That would make this a lot easier.
Unfortunately, there is no pre-built method for applying WS-Security signing and encryption.
To accomplish WS-Security, I implemented Java code that utilizes the following libraries (Axis2, Axiom, Neethi, Rampart) to consume the endpoints. Among these libraries, Rampart specifically handles the signing and encryption of both incoming and outgoing requests.
I think you are correct in your assessment of the situation and how to work around this. In essence you can probably use something like this as your guide for the basics. But it might turn out to be more complicated than this if the published web service has any additional requirements for the exact format in which the message should be sent.
We use VPN with employee tracking software. Perhaps it will help.