The question of whether a diophantine equation has infinitely many solutions is at least hard as the question of whether a diophantine equation has any solutions, and is therefore undecidable. (As JDH comments below, in a certain technical sense, the question of whether there are infinitely many solutions may be harder.)
Proof: Let $F(x_1, x_2, \ldots, x_m)=0$ be any diophantine equation. Then $F=0$ has a solution if and only if $F(x_1, x_2, \ldots, x_{m-1}, y-z)=0$ has infinitely many solutions.
Your error is equating "infinitely many" with the much larger "all but finitely many".
UPDATE: As Mohammed points out "It is false that all but finitely many bagels are delicious" is equivalent to "infinitely many bagels are not delicious". And the theorem of Marker and Slaman is for all first order statements, not just for diophantine equations, so we should be able to use this rewording.
On skimming their paper, the first thing that I notice is that they have the quantifier $\forall^{\infty}$ ranging over a single integer variable, not over a $k$-tuple of integers, so you can say "For all but finitely many $x$, the following holds for all but finitely many $y$..." but can't directly say the stronger "For all but finitely many ordered pairs $(x,y)$..." But I'm not sure whether this is the heart of the difference, or just a minor technical issue.