Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output predicted by a NEXP machine, i.e. $P^A\subseteq$ NEXP. We adopt the convention that if P submits a query which doesn't satisfy the promise of A (that is, $x\not\in A_{YES}\cup A_{NO}$), then the oracle for A randomly returns 0 or 1 $^*$. Suppose further that for all valid queries (i.e. those satisfying the promise, $x\in A_{YES}\cup A_{NO}$) there exists a single witness which (when run by an EXP machine) allows all queries to the oracle A to be predicted. Finally, let it is be trivial (i.e. in P) to determine whether a query $x$ satisfies the promise or not. Then is it correct to say $P^A\subseteq$ NEXP?
If the P machine were guaranteed to only make valid queries, then it seems like this is trivial as the NEXP machine is (by assumption) capable of simulating the oracle outcomes and any processing done by the P machine. However, the fact that the P machine can make invalid queries which return 0 or 1 randomly could potentially throw a problem in the simulation.
So far all I've found is Oded Goldreich's notes on promise problems. These don't give a direct answer, but do introduce smart reductions: http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf Smart reductions seem to force the P machine to only make valid queries. So in this case it would perhaps be correct to say $P_S^A\subseteq$NEXP, where $P_S$ is a ``smart TM'' which only makes valid queries. But is it correct to state the stronger result that $P^A\subseteq$NEXP?
$^*$As I understand it, this is standard (see the link to Oded Goldreich's notes above).