I'm looking for a Ajax/TreeGrid (Tree with multiple columns) implementation.
It has to:
I tried Dojo (dojox.grid.LazyTreeGrid) and it seems to have problems with pagination.
ExtJS's TreeGrid meets all your criteria except for the last one. Our implementation uses server-side sorting and on-demand loading/creating/deleting/moving of child nodes on the client, and then we push that data back to the server for persistance.
Ext is a huge framework, but you can take advantage of their dynamic loading to keep your page load times short.
You can download it for free to see if it's a good fit and perhaps decide if it's worth licensing.