Are there adversarial inputs for randomized quicksort?

Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort runs in $O(n \log n)$ time with high probability. (See, for example, the book Randomized Algorithms by Motwani&Raghavan.) I am refering to the version of randomized quicksort that picks the pivot uniformly at random at each recursive call.

So my question is: are there indeed adversarial inputs for randomized quicksort? Please give an intuitive reason as to why such an input can exist.

Update. It seems to me that the adversary in the paper is granted unrealistic capabilities (generate array on the fly), which explains why it can make any quicksort perform poorly. Under reasonable assumptions I would say there is indeed no adversarial input for randomized quicksort.

There are implementations of Quicksort (the partitioning algorithm, specifically) which deal badly with duplicates. No matter how much you randomize -- shuffling the input, random choice of the pivot, random choice of the pivot with sampling, ... -- if all entries are the same (or there are only constantly many distinct values), these bad implementations will result in worst-case behaviour, always.

You can find details e.g. here and in the literature.

Note bene: The reason why many TCSists would claim the opposite with a passion it that they forget that most classical analyses are performed under permutation models. That does not give the whole truth, though, particularly if you use sorting in practice. Duplicates are relevant, for instance if you sort lists of binary values.

StackExchange Computer Science Q#55382, answer score: 8