I'm not sure there is any level of black-box evidence that could convince me they were telling the truth.

I'm afraid I can't do much better at this point than to cite Harvey Friedman's position on this. (He posted his alien crystall ball scenario before I posted my alien black box, and obviously knows a lot more about this stuff than I do.)

I now come to the various deep questions - conceptually and technically - that arise when attempting to make "proofs" that the Crystal Ball from the hyperaliens is "the real thing" and that the information gleaned from its use is "proved".

I believe very strongly that rather subtle probabilistic arguments combined with rather clever TMs, will show, in various "rigorous" senses, that the Crystal Ball is the real thing (provided it is in fact the real thing).

Here are the relevant discussion threads on the Foundations of Mathematics mailing list:

• http://cs.nyu.edu/pipermail/fom/2004-February/subject.html#7934
• http://cs.nyu.edu/pipermail/fom/2004-March/subject.html#8003

ETA:

In the case of a halting oracle, the problem there is no point where it would seem that such a ridiculous cheat would be even harder than doing it correctly.

Assuming the laws of physics actually does allow a halting oracle to be implemented, then at some point it would be easier to just implement it than to do these ridiculous cheats, right? As we rule out various possible cheats, that intuitively raises our credence that a halting oracle can be physically implemented, which contradicts the universal prior.