In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "doubly periodic") is undecidable. The analogous coloring problem is well known to be NP-complete (for $k \geq 3$ when restricted to finite graphs).

Burr also proves that certain graph-theoretic Ramsey coloring problems are undecidable for certain infinite graphs. Separately, Burr proved that the analogous Ramsey coloring problems are NP-complete when restricted to finite graphs.

Towards the end of the paper, Burr says that this is a common theme - namely, that infinite generalizations of NP-complete problems tend to be undecidable. He mentions that he does not know such an infinite analog for the traveling salesmen problem, so he did not have in mind any uniform construction that generalizes such finite problems into infinite problems.

What are some other examples of this phenomenon? I know of this paper of Freedman that tells such a story for 3-SAT, but I am not aware of other examples.