We will show where your intuitive argument breaks down. Call the conjecture $\varphi$, and suppose that $\varphi$ is undecidable. Then, as you observed, under your very strong assumptions, $\varphi$ is true in the natural numbers, but not provable.
Not provable in what theory? By undecidable we always mean undecidable in a particular theory. Say that theory is PA, first-order Peano Arithmetic. But for the rest of this post, PA could be replaced by any strong enough theory that has the natural numbers as a model.
Let us add to PA the axiom $\lnot\varphi$ as you specified. Then the theory $T$ with axioms the axioms of Peano Arithmetic, together with $\lnot\varphi$, is consistent, and therefore has a model $M$. In $M$, the conjecture $\varphi$ is false.
This model $M$ is not (isomorphic to) $\mathbb{N}$, since $\varphi$ is true in $\mathbb{N}$. The object $\omega\in M$ that "witnesses" the falsity of $\varphi$ in $M$ is therefore not a natural number. Your algorithm will not be applicable to $\omega$, which is, in the informal sense, greater than $1$, $1+1$, $1+1+1$, and so on. (We can without loss of generality assume that $\mathbb{N}\subset M$). Informally, under your assumptions, any $\omega$ that witnesses the falsity of $\varphi$ in $M$ must be an "infinite" integer.
If a certain argument breaks down, it is still possible that the result one is after is true! However, we can find explicit examples of sentences $\varphi$ of the type you described that turn out to be undecidable in PA.
In particular, one can construct an explicit Diophantine equation $E$ (in $k$ variables, where $k$ is not very large, last I heard about $20$) which has no solutions in $\mathbb{N}$, but such that this fact is not provable in PA. Let $\varphi$ be the assertion that this Diophantine equation has no solutions. For any specific $k$-tuple $(a_1,a_2, \dots, a_k)$ of natural numbers, the fact that $(a_1,a_2,\dots,a_k)$ is not a solution of $E$ is easily checkable, by a computation of predictable length. By suitably encoding the $k$-tuples of natural numbers, we can make sure that $\varphi$ satisfies your conditions.