I once had a MP3 player where “random” actually did what it said (for some value of “actually”), including playing the same song twice in a row once in a while.
I did too (up to and including the "some value of actually," as it played 20% of the songs 90% of the time), which is why I brought up that example. It annoyed me to no end that the button did what it said it did.
In general, interfaces should reflect what the user expects the interface to be, rather than what the designer expects the user to interpret the interface to be.
The chapter on judgment under uncertainty in the (excellent) new Oxford Handbook of Cognitive Psychology has a handy little section on recent critiques of the "heuristics and biases" tradition. It also discusses problems with the somewhat-competing "fast and frugal heuristics" school of thought, but for now let me just quote the section on heuristics and biases (pp. 608-609):
My thanks to MIRI intern Stephen Barnes for transcribing this text.