For this client, we have one tip that reveals hidden knowledge of how to work with certificates:
System.setProperty("org.apache.axis.components.net.SecureSocketFactory",org.apache.axis.components.net.SunFakeTrustSocketFactory");
The code above uses a fake trust manager trusting all certificates. This Java SOAP client also worked for us.