I feel this is a bit of an artifact of the problem statement though -- I feel a more "realistic" scenario is that we are given a block box which which is either an oracle, or is correct for programs <N and returns arbitrary answers (sometimes correct, sometimes not) for longer programs.
If false oracles are wrong 50% of the time for length > N, you can run the test program X times, and have 1/2^X odds of it being a false oracle if it matches each time. Obviously, if the test program fails, you now know N is less than the test program's length.
So, if you run the test program 4 times, odds are 1/16 that the oracle is fake, and 15/16 that it is real. For any "realistic" scenario, there's a probability of even a regular computer program failing due to hardware glitches, so you'll eventually approach the same confidence you'd have...
Here's something I've been wondering about, in the context of Solomonoff induction and uncomputable sequences.
I have a device that is either a halting oracle, or an ordinary Turing machine which gives the correct answer to the halting problem for all programs smaller than some finite length N but always outputs "does not halt" when asked to evaluate programs larger than N. If you don't know what N is and you don't have infinite time, is there a way to tell the difference between the actual halting oracle (which gives correct answers for all possible programs) and a "fake" halting oracle which starts giving wrong answers for some N that just happens to be larger than any program that you've tested so far?
The Kolmogorov complexity of an uncomputable sequence is infinite, so Solomonoff induction assigns it a probability of zero, but there's always a computable number with less than epsilon error, so would this ever actually matter?