Lars,
If you look on your CallManager at the file c:\ciscowebs\user\xmldirectorylist.asp you can see how I solved this problem for the built in corporate directory.
I used the http refresh header to pass the next starting record number. When the user presses more then "Next" the phone will request the refresh URL and pass the starting record number. You would then re-query the your directory and jump to the desired start position.
Darrick