hajek showed in http://web.mit.edu/6.435/www/Hajek88.pdf that there are conditions under which an annealing process is guaranteed to find the global minimum. these constraints are pretty tight, but one that's obviously practical to relax is that on the optimality of the solution. a lot of heuristic searches are successful even without finding that global minimum.
so could we ever guarantee finding a solution in the best 1% of all solutions? we may not know much about the distribution of the solutions to this nonconvex problem - not even their number. (my problem is planar graph k-partitioning, but hajek's finding is not limited to any certain problem, as far as i can tell.)
collecting statistics to describe the 1% threshhold seems challenging: states we know about are the ones we've visited, a terrible selection bias; and we can't generate truly random ones. knuth warned not to assume that states reached by random processes will be randomly distributed. we are running the search precisely because we don't know about the global minimum.
perhaps someone else sees another way to extend hajek's finding in this direction?