Have you tried using Visual Studio 2008's "Add Service Reference" feature? If the Java service exposes appropriate metadata, you should hopefully find that the WS-Address and WS-Security headers are taken care of for you automatically.
-steve
Brain.Save() -- http://hyperthink.net/blog