Changing the following-sibling::Record[0] to [1], the recursion works
perfectly however when it has reached the last Record, it goes back to
the top (but peculiarly skips the top record) and does this many
times.

<Record 1 A=1 B=0 C=0>
<Record 2 A=1 B=1 C=0>
<Record 3 A=0 B=0 C=3>
<Record 4 A=0 B=0 C=9>
<Record 2 A=1 B=1 C=0>        <!-- has started again!
<Record 3 A=0 B=0 C=3>
    ... etc. Then starts over at record 3, skipping 1 and 2.

<xsl:apply-templates select="$services//Record">

You don't show the definition of $services, but I assume that
$services//Record selects all the Records. (// is an expensive
operation, if you know your Record elemenst are not arbitrarily deep in
teh eleemnt structure, using somethng other than // will save the system
the effort of looking)

                       <xsl:apply-templates
         select="following-sibling::Record[0]">

I don't think you want to apply templates to siblings as you have
already applied templates to all Record elements in the call above.
This XPath will never select anything as [0] is [position()=0] and
position() always returns an integer >= 1.

David