Technically you could "theoretically" do 100%, but the amount of wasted calls would be tremendous -- that's why I put ~99% as a feasible limit that could be achieved.
Are sequence numbers ever skipped? If not, could you count up from 0 and stop when there's no return? (Side problem: how do you handle when the API "hiccups" and says there are no results but really there are if you ask again in 20 minutes?)