Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?
Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons.

Suppose $x_{(1)},\dots,x_{(n)}$ denotes the elements in sorted order.  Then if you don't see a comparison between $x_{(1)}$ and $x_{(2)}$, you will have no way to tell which order they should appear in.  The same is true of every pair of adjacent element.  So, there are $n-1$ coupons (one per adjacent pair of elements), and you need to collect them all.  Based on the coupon collector problem, we know you'll need $\Theta(n \log n)$ randomly chosen coupons before we've collected them all.  Each observation has a $2/n$ chance of being a coupon, so in total we'll need $\Theta(n^2 \log n)$ observations before we've collected all the coupons.  If we collect all the coupons, we can sort the $x$'s; if we're missing any coupon, we can't sort them.

The subsequent questions boil down to facts about the coupon collector problem, and you can use the tail bounds on Wikipedia to bound the information about the distribution.

If comparisons are chosen without replacement, then you need $\Theta(n^2)$ observations.

A reasonable way to check whether the list is sortable is to do a topological sort, then check that you've observed a comparison between every pair of adjacent items in the topologically sorted order.