What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem?
The idea you mention is covered in complexity theory by probabilistic classes. 

The computational model they refer to is the probabilistic Turing machine, i.e. a Turing machine equipped with an additional read only tape that at the beginning of the computation contains an infinite sequence of symbols, independently chosen at random with uniform probability from the machine alphabet. Or, equivalently, a Turing machine that can flip a fair coin and read the answer in constant time.

Observe that due to the way that our computational model works, two executions on the same instance may give two different answers; for instance, one could define a machine that flips a coin and returns YES on heads and NO on tails.

We are interested in both the asymptotic worst-case running time and the probability that the answer given is actually correct. In literature, a vast amount of different classes are analyzed, they differ depending on various constraints that they impose on the solver.

Perhaps the most interesting of such classes, both from a theoretical and practical point of view is $\mathcal{BPP}$, defined as the class of languages decidable in polynomial time by a probabilistic Turing machine that, whether the answer is YES or NO, is guaranteed to give a correct answer with probability at least $2/3$. Notably, it is an open problem whether or not $\mathcal{P} = \mathcal{BPP}$.

A full discussion of probabilistic complexity theory would be too lengthy for SE, although there are plenty of sources available in both electronic and dead-tree form.