From the OP: "you don't know what N is." But, yes, you don't have to do the "step simulation", you are right. You can just check a single known halting program of every length, starting at 1, and increasing. Eventually you will catch the oracle in a lie.
See also: thomblake's comment below, which gives the same algorithm.
This is not a decision algorithm: if the oracle actually is real, your program will never terminate.
Edit: I guess you realize this already, but there are a few confused comments from other people here, so I will not retract this.
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?