I've made large joins faster in MySQL by adding gratuitous order by to derived table queries, which lead to probing the index in the join in index order instead of a different, more random, order. The cost of the extra redundant sort was less than the cost of the random btree traversals.
Implicit ordering can outsource it to users and result in some awful to use software.
I think I've told this story before here but the best bug I've ever fixed is adding an order by clause to a query. The client was trying to find items in a combo box that were essentially randomly ordered, it was literally taking hours out of their day to find stuff in this list and forcing them to do overtime to keep up with the workload, they literally cried when I fixed it. I had to sneak the change past management but I'm not sure if I was successful, it may have played a role in my short tenure there.
That's a particularly bad example but like perl4ever I've found this to be more common and in practice a much bigger deal than gratuitous order by clauses.
I've seen many variations where the natural ordering is fine but once it's combined with top, or joined, or filtered the results become very random to users.