Since quantum algorithms are inherently random, these three problems qualify:

1. Solve the Deutsch-Jozsa problem in constant time.
2. Search an unstructured database in O(sqrt(n)) time.
3. Factorize integers in polynomial time.

Moreover, randomized algorithms are occasionally useful in a classical computer, since they give good expected performance even for some classes of degenerate inputs.

Which instance of "random" do you think should have been pseudo random? The instance I quoted. But as I said the point is trivial.

So you are saying that the sentence "Computer programmes can consult random-number generators where needed, including 'real' ones implemented in hardware." Should have read "Computer programmes can consult pseudo- random-number generators where needed, including 'real' ones implemented in hardware". Are you aware that your change renders the sentence contradictory? The point of real randomness generators is that, given certain assumptions about physics, they are not pseudo?

I don't think I used the word "mistake",

If you had used it, I would have had no need to ask the question. I was trying to put you vaguely negative comments about the use of randomness in software on a more precise basis.

Besides encryption which depends on secrecy and therefore depends on not knowing what will come out,

I dont see why an example that works should be excluded becuase it works.

Another example I like is the way ethernet works: when two MAC's try to send simultaneously, then result is garbled and they need to back off and retry. However, backing off according to a deterministic algorithm would lead to another collision on the retry, ad infinitum. Backing off for a random time solves that simply.