Using an oracle to find a vector $b$ for which $Ax=b$ has a solution
We can make one observation: adaptive access to the oracle doesn't help.  You might as well fix in advance the set of queries you plan to make to the oracle.  So, the condition is that there has to exist a polynomial-size set of candidate values of $b$, such that it is likely that at least one of those will work.

Why doesn't adaptive access help?  That's because you can assume without loss of generality that every oracle query returns 0.  In other words, given an adaptive algorithm for generating queries, run that algorithm with a fake oracle that always returns "no solution", record the list of queries it makes, and there's a list of candidate values of $b$ that a non-adaptive algorithm can use.  This yields a non-adaptive algorithm that performs as well as the adaptive algorithm.

As a consequence, since you want a deterministic algorithm that always succeeds, a necessary and sufficient condition is that there must exist a polynomial-sized, polynomial-time-constructible set $B \subset \mathbb{Z}_{&gt;0}^m$ such that for all possible matrices $A$ there exists at least one $b \in B$ that works for $A$ (i.e., such that there exists $x$ so that $Ax=b$).