If you're using JAX-WS RI to generate your service client, the only way to get past this shortcoming is to create a SOAPHandler that can intercept and change SOAP headers. The handler needs to look for the MessageID header, which can then be overwritten.
To get this handler to work, two other additions are required. First, a handler-chain.xml file needs to be created that specifies the name of the SOAP handler class we're about to implement. This file needs to be presents on the classpath and be part of the same package as the web service client.
Then the xxxxService class that was generated as part of the web service client needs the following annotation added at class level...
Then comes the fun part, the SOAP handler class itself...
What this handler does is first check whether it's dealing with an outbound message i.e. a message being sent to the web service. This should always be the case for a web service client, but it doesn't hurt to check anyway. Then all of the SOAP headers are checked to see if the MessageID header is one of them. Once the MessageID header is found, it's value is overwritten and set to "http://example.com/my_message_id". Note that the wsa:MessageID must be a URL since it's type is defined as xsd:anyURI in the WS-A specification. Of course you can define how the wsaId is created based on hour requirements.
I found this article and this post useful when coming up with my own solution.