Computability of Kolmogorov Complexity
That's right. You can run all machines in parallel and you'll find shorter and shorter descriptions, but at some point there will always be a shorter program still running, for which you can't prove that it won't halt with $x$ as output.

The probability you describe (of a program not halting, assuming some distribution on inputs) is the complement to Chaitin's omega: the probability that a program will halt. Of course, Chaiting's omega is also not computable and the best way we have of approximating it, is just by running all programs in parallel and summing the probabilities for the ones we've seen halting. 

If you start with a probability distribution on outputs, the probabilities have different bounds. If you take a uniform distribution on strings of length $n$, then as $n \rightarrow \infty$, the proportion of strings compressible by more than a few bits is negligible, ie. $K(x) \approx |x|$ with near certainty for large $n$. If you take the universal distribution, then every computable pattern will appear in your string with some probability.