As Shakespeare notes, sometimes there's method in madness.
Yes, “random order” is an oxymoron in that the two words are an apparent contradiction in terms: order suggests organization while random suggests a lack thereof. However, like many oxymora, the contradiction is incidental and resolvable by careful consideration. “Controlled chaos” is a similar oxymoron where lack of a method is part of the method.
To resolve the contradiction, first consider that order doesn't always mean deliberate order. The natural order is a well-known example, used in contrast to the laws of God and men, where philosophers base morality on the natural world as observed instead of a divine or mortal plan. Spontaneous order is a similar example, where order emerges “out of seeming chaos.” This lies at the root of Tim Lymington's comment that sequence needn't imply deliberation.
Furthermore, the Oxford definition of random overlooks many subtleties of the word, as it's a dictionary and not a comprehensive treatment of the subject. While a random order does imply a lack of conscious choice in selecting each element of the sequence, it does not speak to the choice of employing randomness in the overall method. The process is deliberate (and thus ordered) even if the outcome is not (and thus random).
I don't believe that this is a deliberate oxymoron – emphasis mine:
In general, oxymora can be divided into expressions that were deliberately crafted to be contradictory and those phrases that inadvertently or incidentally contain a contradiction, often as a result of a punning use of one or both words.
Order includes both deliberate and observed sequences. Randomness can indicate a lack of a plan or simply an unpredictable outcome. “Random order” actually means “an observed sequence with unpredictable outcome.” The contradiction only arises incidentally, if you select the wrong meaning of both words to form “a deliberate lack of a plan,” making this an inadvertent oxymoron.