I've implemented this, but there still seems to be a problem with duplicate nodes in the tree, which is causing the updateIndexes function in Ext.view.AbstractView to fail. Specifically, the property this.all.elements at that point, contains two copies of each node (6 in total), while the call to this.store.getRange() return only the three individual records.
What version of ExtJS do you use? It has been tested with 4.0.6 and 4.0.7 only.
And have you done all store (abstract and tree) classes overwrite?
Data format is as for TreeStore, nothing special.
New page request works as node collapse, subnodes remove and node expand with parameter (page). Request MUST return only subnodes of specified node (for given page) - not all tree. When request returns nodes which are in the tree already then you have duplicates. Maybe this is the case?