As long as the number of keys is finite, you (or a computer) can still technically figure out whether your program will halt. The halting problem is semi-decidable and this is a case where you can decide, it just takes a long, long time. Moreover, in this case you can generally say “if one of the keys in the key space decrypts the message to the chosen plaintext, it will halt”.

The Collatz conjecture example on the other hand shows something where we don’t know whether it will halt for all input[1], because we don’t know if the Collatz conjecture is actually true. There are many other things without proof in either direction, some of which may not be able to be proven (Goedel’s incompleteness theorem says that if I’m not mistaken, but I am not a mathematician, please correct me if I’m wrong or inaccurate).

[1] Yes in practice the data types are limited, memory is limited, state in general is limited. So you can always “solve” the halting problem for a “real” computer by just trying out every representable state, even if that takes longer than the universe exists. But Turing machines, which is what the halting problem is defined on, have infinite tape.