This is in fact possible with the OOTB paging. I found the solution by accident while working on a CrossList DVWP.
The origin to the problem is changes that are made to several variables in the DVWP, probably by SPD when turning it into CrossList mode.
An Easy way to get the paging working again is by adding the Grouping toolbar to the dataview from the Options Toolbar icon under the Design tab in SPD.
This will do the necessary changes and the paging will still work even if you remove the toolbar.
Furthermore, I've examined the code and these are the changes between the none-working and the working code:
1. In dvt_1 template, change the LastRow variable to:
<xsl:variable name="LastRow" >
<xsl:choose>
<xsl:when test="($FirstRow + $RowLimit - 1) > $dvt_RowCount"><xsl:value-of select="$dvt_RowCount" /></xsl:when>
<xsl:otherwise><xsl:value-of select="$FirstRow + $RowLimit - 1" /></xsl:otherwise>
</xsl:choose>
</xsl:variable>
2. Still within dvt_1, in the call to dvt1.body, change the Row parameter to:
<xsl:with-param name="Rows" select="$Rows[position() >= $FirstRow and position() <= $LastRow]" />
3. In dvt.CommandFooter, change the test attribute of the first xsl:if tag to:
<xsl:if test="$FirstRow > 1 or $LastRow < $dvt_RowCount">
4. In the SPDatasource Tag, delete the asp:parameters under the SelectParameters tag (StartRowIndex, nextpagedata and MaximumRows)