Here is another interesting scheme, which might be better if your initial classifier has high accuracy. Suppose your classifier has a 99% accuracy, i.e., an 1% error rate. Divide the test set into $N/100$ blocks of 100 data points. We will work on one block at a time, for each block recovering the correct classification of all 100 data points in that block.
Note that we expect about 37% of the blocks to be have no errors (all 100 data points are classified correctly by your classifier), 37% to have one error, and 26% to have two or more errors. We can figure out how many errors are present in a block by making a single query: flip the prediction for all 100 data points in the block (leaving the other $N-100$ predictions unchanged), submit it, and see how much the accuracy decreases. If the number of correct predictions decreases by 100, then the original predictions were all correct; if it decreases by 98, then there was 1 error in the original predictions; otherwise there were 2 or more errors.
Also, you can find the locations of the errors. For instance, if there is a single error, you can find the location of the error by doing binary search: split the block in half, and test whether the error is in the first half or second half by testing the number of errors in the first half. Recurse. This will find the location of a single error using $\lg 100$ submissions on average. In general, if there are $k$ errors in the block, you can find the location of them using at most $k \lg 100$ submissions.
Once you have finished this procedure for a block, you know the correct classification of all points within the block.
Since the number of errors in each block has a Poisson distribution, the average number of errors is 1. Therefore, on average we will do $1 + \lg 100 \approx 7.6$ submissions per block. After $(N/100) \times (1 + \lg 100) \approx 0.076 N$ submissions, you learn the correct classification for all points in the test set. You can of course generalize; if the error rate is $1/m$, then you can use blocks of size $m$, and you'll need about $(N/m) (1 + \lg m)$ submissions to reverse engineer the test set.
This shows that the higher the initial accuracy of your classifier, the fewer number of submissions needed to reverse engineer the correct classification of all data points in the test set.
As a heuristic, you can also recover the correct classification for some number of data points (by processing some of the blocks as above), then add those to your training set, and make new predictions on the remaining data points in the test set. If you are lucky, perhaps your classification accuracy on the remainder will improve (thanks to the additional training data), and perhaps even fewer submissions will be needed.