I was reading this post about whether Cook-Levin relativizes and at the bottom of the answer, they include a quote from Computational Complexity by C. Papadimitriou (this is a longer version of the quote than included in the aforementioned post):
But when we say "$NP^A$-complete," do we also allow the use of oracles in our reductions? With a little reflection we may decide that the right way to state the result is in terms of ordinary reductions (especially since there are difficulites associated with defining space-bounded oracle machines, see the references).
However, I do not see why one would not allow for the use of oracles in reductions when defining $NP^A$-complete. Even accounting for the difficulty of defining space-bounded oracle machines, one could simply use polynomial-time reductions with an oracle instead of logarithmic-space reductions. So what goes wrong when one defines $NP^A$-complete using polynomial-time reductions with the use of oracles?
