As it turns out, that's not always the full story. Although the signing is correctly done this way, the default implementation of WSS4J (which Apache CXF uses) sends timestamps with a millisecond accuracy. Although this is fully in line with the "RECOMMENDED" part of the WS-Security 1.0 specification, it is apparently something that Microsoft did not consider when writing WSE 1.0. As you can read, WSE 1.0 rejects the message if it has a millisecond time stamp.
I did find it quite surprising to find no other reference of this on the internet, except a page on MSDN which describes the "Microsoft.com Web Service".
Luckily, there's a quick way to switch off milliseconds for time stamps in CXF: just add a parameter
"precisionInMilliseconds" with the value "false" to the parameter map of your WSS4JOutInterceptor.