IComparable<T>.CompareTo の注意書きだが
>A.CompareTo(A) は 0 を返す必要があります
なので、少なくとも値型で同じ値のときにランダムな大小結果を返すのは許されないようだ
まさかチェックされるとは思わなかったが
参照型で別インスタンスなら問題ないかもしれんが
>A.CompareTo(B) が 0 以外の値を返す場合、B.CompareTo(A) は反対の符号の値を返す必要があります。
らしいので、完全にランダムってわけにはいかんかもしれん

ソートは基本的には、比較と交換の繰り返しだから、比較で手を入れられないなら
交換するかどうかをランダムにするソートを自作するのが良いんじゃね
ソートの中身なんてアルゴリズムの本とか探せばいくらでもあるだろ