Out of fairness, there is a recent paper on the topic http://dx.doi.org/10.1038/nature16059 by Toby S. Cubitt, David Perez-Garcia, and Michael M. Wolf. Undecidability of the spectral gap. Nature, 2015; 528: 207-211. And that paper claims there are undecidable problems in physics.
But it does so by the exact same hack as the examples you give, i.e. taking an infinite number of problems, grouping them together as one problem and then arguing that you can't make a single solution that works for them all.
I'm not sure how that's physics. Sure, it's nice to have one solution that works for an infinite number of different problems. So it's nice to have when you can have it. But it's hardly an issue when you can't.
And note, the example of the spectral gap, isn't a mere unsolved math problem, it's an undecidable one. Which means no single standard algorithm can solve all of the infinitely many cases.
A truly physical, experimentally falsifiable, question is a specific prediction. It takes a specific setup and generates a specific prediction. One situation. Not infinitely many.
Sure, it can be nice to group a whole bunch of individual situations into a single group, especially if they can be tackled in one go. But they should be grouped together exactly if they can be solved together in one go.
If you can't solve them in one go, then you shouldn't have grouped them together into allegedly one problem. And if you can't solve a specific problem enough to make a prediction, then it isn't really science.
So truly science doesn't have any predictions based on undecidable results. And if a theory in progress depends on an unfinished result, then it is an unfinished theory. In science, a theory is the predictions. You can tell because that's how a theory is rejected, based on its predictions. So until you have the predictions you aren't a theory yet.