Re: WSE464: No policy could be found for this message.

You’re using the WSE adapter?  Have you considered using WCF-WSHttp instead?  In R2, WCF adapters are the way to go and they can solve many of the frustrations with SOAP and WSE.  If you call the WS with a C# client, do you get the error?