What is the theory behind testing fixes for intermittent bugs?
You juggle with "probabilities" without defining any. There are two different questions here.


  For practical programs, can I use random testing to establish that any given execution has close to 100% success probability?


Not in the strict sense, no. Even if input spaces are finite, they are typically huge. Without further information, you'd have to test a lot of inputs (and/or contexts), which is not feasible. As in, solving most NP-complete problems is faster.

You could try to perform statistical testing, that is get some bound on the error for some statistical significance -- but that would assume that you have a model for the error distribution. Which I would be surprised to hear if you had. And even if, it's probably not one of those that mathematicians have bothered to explore. So, ballpark guess, statistical tests are impossible (or meaningless, if you went ahead and did the numbers assuming a normal model or something).


  Can I formalize programs and their execution so that I can make meaningful statements about (stochastic) bug-freeness?


Yes, sure. What you need are


formal semantics,
formal specifications, and
a distribution of inputs.


Then, you can (in principle) prove (not test!) what the expected error rate is. I've never seen it done, though -- probably because it's at least as hard as proving the program correct in the first place.

If you ask me, you are better served with reasonable heuristics and solid processes. Specification testing may be helpful in certain contexts, just because it makes it easy to test many different variants.