If it isn't one thing...
Ok, so I've cleared up the paging issue and have a viable sample to post and show off the fact you can page through over 1500 pages of FSTDT content without any trouble. So I want to FTP it up to the new host... it doesn't fucking work.
I'm hitting them with a support ticket and see how it goes.
That all said, I managed to get it working by effectively pre-populating any possible combination of filters rather than ignoring turned off filters. I thought this would be a huge amount of data, and for this place it is. But it's size totals out to all of 8 megs of a table including an index that restates the content of the table in the order I want it to... so yeah, that's a wonderful damn thing right there. Almost no size for a damn nice improvement in speed. For reference the similar index on the current site is around 250 megs, but it has to include a great deal more data to offer anywhere near the same amount of speed.
Next stop after cursing support out is playing with the search functionality, even if I'm not going to renew with these guys at the end of the month I can get some testing done.