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, Alexei Miasnikov and I proved that the halting problem itself admits a black 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.
[Edit: A bug in the original proof has been fixed, thanks to a comment by Francois Dorais.]
The answer is no. This kind of thing can be proved by what I call a "gas tank" argument. First enumerate all Turing machines in some manner $N_1, N_2, N_3, \ldots$ Then construct a sequence of Turing machines $M_1, M_2, M_3, \ldots$ as follows. On an input of length $n$, $M_i$ simulates $N_i$ (on empty input) for up to $n$ steps. If $N_i$ does not halt within that time, then $M_i$ halts immediately after the $n$th step. However, if $N_i$ halts within the first $n$ steps, then $M_i$ "runs out of gas" and starts behaving erratically, which in this context means (say) that it continues running for $n^e$ steps before halting where $e$ is the number of steps that $N_i$ took to halt.
Now if we had a program $P$ that could compute a polynomial upper bound on any polytime machine, then we could determine whether $N_i$ halts by calling $P$ on $M_i$, reading off the exponent $e$, and simulating $N_i$ for (at most) $e$ steps. If $N_i$ doesn't halt by then, then we know it will never halt.
Of course this proof technique is very general; for example, $M_i$ can be made to simulate any fixed $M$ as long as it has gas but then do something else when it runs out of gas, proving that it will be undecidable whether an arbitrary given machine behaves like $M$.
Best Answer
Here is one way of interpreting your question. In my joint paper:
the main theorem is that for some of the standard models of computation, the halting problem is decidable with probability one. Specifically, we prove that for the usual one-way-infinite Turing machine model, there is a set $A$ of Turing machine programs, such that:
So this is a sense in which the halting problem is decidable with probability one.
The argument is sensitive, however, to the computational model, and for some other models of computation, the best currently known is that we can decide the halting problem on a set of probability $\frac 1{e^2}$, which is about 13.5%.