The first 1000 pages appear to be indexed correctly no pages appear to have been skipped at this point. The problem appears after around 1500 pages are indexed, for some reason it then stops adding any more after this (even though it appears to be trying to process them, although according to the web server logs no requests are being made).
For instance the following page is correctly indexed:
/search/holidaysales/Properties-in-Spain/psE10AstpE1AcurE100AcntE309ApoaEtrueAsldEfalse/1/
has a link to the page:
/HS1182487/Salia-2/100/
this is correctly added to the index, but another page that it has indexed:
/search/holidaysales/Properties-in-Spain/psE10AstpE1AcurE100AcntE309ApoaEtrueAsldEfalse/2/
has a link to the page:
/HS1132529/La-Ciguena/100/
But for some reason this page never gets added to the index.
It is as if something is causing the xml site map generator to stop making requests for pages, even though it appears to be processing them.