Discussed this offline, but for anyone else reading the forums.
Currently Domino web services don't support the client authentication mechanism. Related SPRs (in case anyone needs to subscribe to an APAR).
SODY9H6BTM - Relates to Client Authentication using the SOAP classes in Domino.
SODY9GJDBB - Relates to Client Authentication using Web Services (ie. import WSDL) in Domino.
Using the Apache Axis third party jars should act as a work around.