1. I have no idea which compatibility issues could be encountered when using WS-Policy inside the WSDL. This suggestion sounds interesting. May be your client could provide some examples of such incompatibilities.
2. I solved similar problem recently. WS-Policy entries inside the WSDL was not an issue. But it was required to use custom algorithm suite for signing. Consequently I got stuck on undesirable Spring dependency when tried to provide Apache CXF with custom AlgorithmSuite. So I abandoned this way and made the following workaround:
a. Got rid of WS-Policy entries inside the WSDL and left my web service WSS-unaware.
b. Made another servlet (in form of REST service) which acts as a signing proxy for the web service. It does two things: patches original WSDL with the actual location when WSDL is requested and signs original application responses. Signature validation for incoming application requests is optional in my case.