Ah, interesting, I missed that detail. Yes, you may already be aware that there's a whole hierarchy of undecidable problems, where if you have an oracle for undecidable problem X, you may be able to decide an otherwise undecidable problem Y, but still not Z, etc.
Indeed; it's related to the whole tower of large numbers etc. There's no escaping the Halting Problem. It's just a matter of which level of halting "bites us".
Anyway, I hope I've convinced you that the appeal to physics is inside "Turing Machines are a reasonable model of how computations work." It's so weird to think about other more powerful machines exactly because they go against deeply-ingrained intuition about what the world is really like.
Moreover, physics really seems to prevent you from doing any "sick" by monkeying around either on the quantum or gravitational side. Did the laws of physics have to do that? I have no idea.
Perhaps someday we'll wind up elevating the (extended, quantum) Church-Turing thesis to a physical principle and rule out classes of physical law because they'd lead to violations of computational difficulty, in much the same way we rule out classes of physical law because they lead to violations of conservation of energy.
