How do you use tabledrag API in a multi-page environment?
I doubt anyone else will have a useful answer. But the DraggableViews module for Drupal 6 showed 3 items from the previous and next Page(s) in paged results. Allowing you to drag an item from the previous page into the previous or next page.

Now if you have hundreds of items I'm not sure how you would skip multiple pages at once -- but looking at how they did this could help you to extend the Drupal 7 Draggable Views module to achieve the functionality you want.

Unfortunately the Drupal 7 DraggableViews does not support this yet.

Proof of this is in this issue queue:
https://www.drupal.org/node/1458870