As someone not intimately familiar with xml wouldn't xs:all do what you need? It provides unordered but required.
I spent a few days trying to get a schema working with our format. I had it working well enough with a specific node ordering, but when I tried to get it working with an order-agnostic set it would all break down around you.
That's when I threw out two full days of work and replaced it with a Java class I spent about an hour writing and testing. Working flawlessly ever since.