You are right that you are trying to do something that isn't one of the things that W3C XML Schema is best at. There are a few options you could try, depending on what is politically and technically acceptable for your project:
* you could try an alternative schema language. Schematron can certainly do what you want, and I suspect RELAX NG could as well;
* you could write a custom validator. For example, for this problem, you only need to check the child elements of . That's fairly easy to write a custom/bespoke validator for, using SAX or StAX. You could also write an XPath based validator (which would work a bit like Schematron).
Anthony B. Coates
Author, XML APIs Chapter
Advanced XML Applications from the Experts at The XML Guild