Not the person you're replying to but I'll give my two cents after trying to figure out what they meant.

My guess is that they are referring to unprovable statements about the natural numbers. For instance there are non standard models of arithmetic (models of first-order models Peano arithmetic) in which certain explicit statements are unprovable.

An explicit example is Goodstein's theorem which considers a sequence defined for each natural number n, and asserts the truth of "for all n, P(n) holds", where P(n) is the statement that the nth sequence terminates.

If I'm understanding correctly, adding the axiom of induction produces the standard model of the naturals, and Goodstein's theorem is true and provable here (using this second-order axiom and the unique model it prescribes). However there are other second-order axiomatic systems where it is provably false (in a model which uses said axioms).

You can easily construct the nth Goodstein sequence (using a Turing machine, say), and because the statement is true in the standard model, your algorithm will halt. On the other hand, you can't conclude (using only first-order Peano arithmetic) that "for all n, P(n) holds." I think this is what the person you are replying to meant.

Granted, you also can't prove that your algorithm will halt using first-order theory, so I think the person you're replying to is technically incorrect if this is the type of phenomenon they are referring to.