Your question is about many things, but let me give an answer focused on just one interesting issue, the question of determining how long a program will run.
The busy beaver function exactly measures how long programs of a given size run before halting (among the ones that do halt). There are versions of the busy beaver function for any notion of computation, but let us consider the case of C programs, since you mentioned them. Note that for any natural number $n$, there are an enormous number of C programs of size $n$, measured in kilobytes, say. Nevertheless, this enormous number is finite. Among all programs of size at most $n$, some halt and some do not. Define $b(n)$ to be the running time in clock cycles of the longest-running but halting C program of size at most $n$.
The interesting thing is that the busy beaver function is not computable! If we had a way of computing $b$, then we would be able to solve the halting problem, since given any C program, we look at its size $n$, compute $b(n)$ and run the program for that many steps; it it hasn't halted by then, we know it will never halt. Another way to say this is that if we have an oracle black-box that allows us somehow to compute the function $b$, then we would be able to answer any halting problem query. Since it is impossible to solve the halting problem, it follows that we cannot compute the busy beaver function.
Edit. In your update, you mention the problem of solving the halting problem 99.99% of the time. The general problem of solving almost all instances of a problem, as opposed to all instances of a problem, gives rise to the subject known as generic case complexity. In particular, the black-hole phenomenon occurs when the difficulty of an unsolvable or infeasible problem is concentrated in a very tiny region, outside of which it is easy. It is not good, for example, to base an encryption scheme on a problem whose difficulty has high worst-case complexity, but whose average-case complexitty is low, for if the robbers can rob the bank 10% of the time, it is good enough for them.
In fact, Alexie Alexei Miasnikov and I proved that the halting problem itself admits a black hold---for hole---for some of the standard computation models, there is a method to solve the halting problem with probability $1$, using the natural asymptotic density measure on the space of programs. I explain further details in this MO answer.
