One would think that if order mattered, your clients would have specified it in a schema or some-such mechanism.

Well, it's a Microsoft protocol. The fact that there's any public documentation at all is something of a surprise to me. The protocol examples - and, indeed, the on-the-wire traffic - specifies namespace URLs which don't work.

Regardless, you may be bumping up against limitations in your processing library. Consider python, as its library is pretty robust.

Nah. The library is robust. It's that it hasn't got a way of preserving order. There's a more complex library to do that, and really for the amount of XML I'm generating it's easier to hand-code it. And really now. Changing the entire language I'm using (which would, incidentally, require me to learn a whole new language AND a library API) just because of some minor failing in the existing library? Seems a bit overkill...