[xsl] How to sort sibling elements based on attribute of child element

[Philip Steiner <redveedub@xxxxxxxxx>]

Given:

<Root>
    <Stuff>stuff</Stuff>
    <Annotation>
        <Comment Priority="1">my first comment</Comment>
    </Annotation>
    <Annotation>
        <Comment Priority="3">my third comment</Comment>
    </Annotation>
    <Annotation>
        <Comment Priority="2">my second comment</Comment>
    </Annotation>
    <Bother>bother</Bother>
</Root>

Using XSL 1.0 / MSXML6.0, I want to produce the Annotation elements
sorted by @Priority, e.g.

stuff
my first comment
my second comment
my third comment
bother

Constraints:

1. Preceding and following elements e.g. <Stuff> and <Bother>, and
possibly other elements, are optional in the source XML, but must be
output in sequence wrt comments
2. The parent element (i.e. <Root>) may have a different name
3. The child element of <Annotation> may have a different name, e.g. <Note>
4. <Comment> may have one or more sibling elements within <Annotation>, e.g.

<Annotation>
    <Comment Priority="1">comment</Comment>
    <Metadata>blah</Metadata>
</Annotation

I tried this:

<xsl:template match select="Annotation">
    <xsl:apply-templates select="*">
        <xsl:sort select="*/@Priority"/>
    </xsl:apply-templates>
</xsl:template match>

which of course fails because there's only ever one "*/@Priority" for
each Annotation.

And this:

<xsl:template match select="Root">
    <xsl:apply-templates select="*">
        <xsl:sort select="*/@Priority"/>
    </xsl:apply-templates>
</xsl:template match>

which produces:

stuff
bother
my first comment
my second comment
my third comment

which produces the <Comment> elements in the correct order but out of
sequence with their sibling elements.

Any ideas?

Thanks

Philip