> Is it possible you meant <xs:sequence> rather than <xs:choice>? I don't
> believe the question mentioned choice.

No, I meant choice. Basically the original question was: can we allow 
elements in any order, but allow multiples of one of those elements:

   interleave(foo, bar+, baz)

Unfortunately you cannot do

   xs:all(foo, bar+, baz)

Because bar+ is not permitted. To accomplish any order and multiples you 
have to simplify the constraint and do:

   (foo | bar | baz)*

Unfortunately this has the side-effect that multiple foo and multiple 
bar elements are allowed. It is a catch-22... but RelaxNG's interleave 
does exactly the right thing. So, to summarize, the original poster has 
three options

(1) Give up on the "any order" approach and use an <xs:sequence>

(2) Allow multiples of all of the elements and use a repeated 
<xs:choice> (i.e., set maxOccurs to unbounded). This was what I suggested

(3) Give up on XML Schema and DTDs, and use RelaxNG instead

xs:all will not allow multiples of a single child element in the 
<xs:all> children components.

Sorry if I was unclear before... I can clarify further if need be.

All the best,
Jeff Rafter