If you are talking about WS-Security signatures, I believe that the certificate is passed along with your message. The signature will be verified against that assuming it trusts your cert.
WS-Security is a major pain. If you are getting signature invalid, my guess is that there is something wrong with they way it was signed. When I was last involved in this, we had issues with whitespace in the XML. What I recall was that the digest was generated from the indented message but what we actually sent was formatted differently and therefore could not be verified. Whitespace is significant in XML-signatures. My advice to you is to remove any non-content whitespace (tabs, spaces, newlines, etc.) from the XML prior to doing anything else.