With regard to comment, the proof of effectiveness of Monte Carlo algorithms like this is a little thorny- if you look at the wikipedia page, you will see that a proof of statistical consistency for any Monte Carlo algorithms took a long time:
From 1950 to 1996, all the publications on Sequential Monte Carlo methodologies, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic-like algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and on genealogical and ancestral tree based algorithms. The mathematical foundations and the first rigorous analysis of these particle algorithms were written by Pierre Del Moral in 1996.
Here is a possibly more general reference by Del Moral in 1998. The paper is somewhat dense and I am not an expert in the field so I don't think I'll do it justice, but I think that we could probably figure out a similar mathematical proof for random motif search given time and the right problem formulation.
I sense that your concern might be with Monte Carlo algorithms generally rather than random motif search specifically, so hopefully that gets close to your question.
It does look like people have done heuristic analysis of similar algorithms, but they are not formal proofs.
I believe that you are more or less correct.
For example, this presentation's walkthrough of the algorithm (slides 35-36) specifically refers to Greedy randomized profile motif searches. By making the greediness of the algorithm explicit, we can see that there is no claim of finding an optimal solution in any particular iteration, thus the need for multiple retries to get somewhere close to approximate solution.
One additional point made in that presentation is that this algorithm works best when coupled to approaches such as Gibbs sampling for targeting the sampled k-mer chain in regions with higher scores (less entropic k-mers).
A different learning resource with similar content (and a little more intuition) is available here.