That is the case for every possible method that has only oracle access and no bounds.
You either need to do away with the oracle model (e.g. interval arithmetic) or need to provide explicit bounds. For example, bounds could look like: Each evaluation gives you
r=r(x)>0 such that the function is L-Lipschitz in the ball
B_r(x). Then you are guaranteed an approximation on compact domains in finitely many oracle calls. Note that AD can give speedups but cannot help you jump from “undecidable problem” to “decidable”.
Unqualified smoothness without explicit estimates is meaningless in most contexts (polynomials are dense; not even analyticity can help you!).
Edit: Lipschitz is overkill. You need access to the modulus of absolute continuity in a small but finite compact neighborhood. Local Hoelder is totally fine as an alternative.