I have run into a similar problem.  My solution, such as it was, was
to essentially run multiple passes over the data.  Something like

  <xsl:variable name='records'>
    <xsl:for-each ...>
      <record .../>
    </xsl:for-each>
  </xsl:variable>

  <h1>First Half</h1>
  <div>
    <ul>
      <xsl:for-each select='xxx:nodeset($records)/record[position() &lt; (count(xxx:nodeset($records)) div 2)]'>
        <li> ... </li>
      </xsl:for-each>
    </ul>
  </div>

Something like that, ignoring typos and other bugs.  You'll need to
use a nodeset extension (I'm using Xalan) since you're apparently
using XSLT1.

-- 

joe