Searching around, I found this article:
http://www-106.ibm.com/developerworks/webservices/library/ws-sqzsoap.html#code2
This basically add gzip to both end of the connection so that things gets smaller in the stream.
The concept seems to be good. Is something Axis already implemented, so that I can just set a flag to say: use gzip on both the client and server? The idea of modifying Axis code doesn't sound well to me because with every new release of Axis, I have to again apply the patch.