Foros del web, para los que viven de bits

Hola a todos, espero que puedan ayudarme, el problema radica que donde trabajo desarrollamos en .NET, uno de nuestros clientes requiere que le proporcionemos información a través de un Web Services, el problema es que ellos desarrollan en JAVA y nos indican que ya pudieron leer los XML'S que les generamos pero como lo leen por caracter se les complica mucho que la información sea de tamaño variable.

¿Qué podemos hacer para solucionar el problema si ninguno de los dos puede cambiar su plataforma de desarrollo, además de que se supone que para eso existens los Web Services no?

Gracias