I suspect that the answer to your question hinges more on how you understand the word stochastic than any particular insight about optimization.
Multiplicity of optima
In the example you gave, we have an optimization problem that has multiple optima. This is a fairly common situation in discrete optimization problems such as integer programs; it can also occur in nonlinear programming.
In designing optimization algorithms, we typically do not concern ourselves with multiple optima. There are cases, such as LP, where you can inspect the final tableau and state whether there are multiple optima and provide them upon request, but this is more of a "cool feature" than an "essential requirement" of a solution algorithm.
So, why aren't multiple optima a big deal?
Well, if you made your objective function correctly—that is, if it truly orders the feasible solutions according to your preferences—then if a problem has multiple optima, you are by definition indifferent between them. Therefore, it shouldn't matter to you whether the solver produces any one of the multiple optima, or selects randomly from among them, or picks the highest one according to a lexicographical tiebreaking rule like you proposed, or something else.
Viewing multiple optima stochastically
In general, the "solution" to an optimization problem is the set of solutions that provide the optimal objective function value. This set can be empty, or have multiple elements, or be a singularity. Only if it is a singularity do we say that the problem has a unique optimal solution.
You argue that when the optimal solution set has many elements, we can "view" this set stochastically. But this is true only inasmuch as we can view any set stochastically, namely, by imposing a probability distribution over its elements and claiming that we can sample from it, calculate its CDF, etc. The question you should ponder is, What do we stand to gain by introducing these additional parameters? More specifically:
- What probability distribution over the optima makes sense?
- Do you want a solver to actually do this random sampling? How? Why?
- Is a random sample from the optimal solution set preferable, in some sense, to a specific or arbitrarily chosen element of the optimal solution set?
If the answer to the last question is yes, then I would suggest that there is a more fundamental issue with your optimization model: You have defined the feasible solution set and/or objective function in a way that does not truly incorporate all of your preferences.
One situation where multiple optima may be meaningful
One application of optimization is Lagrangian mechanics: By the laws of physics, systems tend to come to rest in the position that minimizes their potential energy, and this equilibrium state can therefore be modeled as an optimization problem. But the process by which the system equilibrates is, essentially, random: Random perturbations to the system knock it this way and that until it converges to a stable state. So, if a mechanical system has multiple equilibria, it may be meaningful to talk about the probability with which it attains each equilibrium according to the kinds of random perturbation present in the environment.
On the other hand, real-world systems are continuous, rather than discrete, and therefore the odds of having two solutions with exactly the same optimal potential energy is vanishingly rare. A more typical outcome would be that the potential energy is nonconvex in the parameters, and there are multiple local optima which can still represent an equilibrium state. Enumeration the local optima of a nonconvex problem is an hard problem in its own right, before we even get to speculating about the probability with which each equilibrium arises.
(I am not a physicist, so I invite any edits that improve the terminology used here.)
This isn't really related to the ideas above, but because you brought up the knapsack problem, it is worth mentioning that one heuristic for solving integer programs is to solve the LP relaxation and treat the $x_i$s as probability values for Bernoulli variables.
By randomly sampling these variables, we can sometimes generate a "pretty good" solution (but, of course, there is no guarantee that it will be optimal or even feasible). But this is different from your example, because you are proposing choosing randomly from among integer solution vectors, whereas the randomized rounding heuristic chooses the elements of the solution vector $x$ randomly and independently.