How again do certain sorting methods use $o(n \log n)$ time?
Radix sort cannot be reduced to a comparison-based sort. If the alphabet is binary, then in some sense you are doing 2-way comparisons, since each bit is either 0 or 1. If there are $n$ numbers of width $w$, radix sort takes time $O(nw)$. Therefore as long as $w \ll \log n$, radix sort will be faster than any comparison-based sort.

What does the condition $w \ll \log n$ mean? If numbers have width $w$ then they are in the range $0$ to $2^w-1$. When $w \ll \log n$, there are less than $n$ possible numbers, so some numbers repeat. In this regime you can beat comparison-based sorting. 

Another algorithm beating comparison-based sorting in the regime in which there are less than $n$ possible number is counting sort. Suppose that the domain is of size $m$. We initialize an array of size $m$, and count how many elements of each type there are. We can then unpack this histogram into the sorted array. This runs in time $O(n+m)$. If $m \ll n$ then this algorithm runs in optimal $O(n)$ time.

In both of these cases, the algorithms cannot be rephrased in the decision-tree model (try doing it!), and so aren't subject to the limitations of comparison-based sorting. No paradoxes here.