It is actually more like $e^{-\sqrt n}$. Let's look at the norm of the inverse matrix. The entries are $\pm\prod_{i:i\ne j}\frac 1{z_j-z_i}\sigma_m(z_1,\dots,z_{j-1},z_{j+1},\dots,z_n)$ where $z_k=e^{2\pi i x_k}$ is a random point on the unit circle and $\sigma_m$ is the $m$-th symmetric sum. Since $\log |Z-z_j|$ has zero mean and finite variance, you expect the first factor to be $e^{O(\sqrt n)}$ most of the time. The size of second factor is essentially the size of the random polynomial $\prod_i(z-z_i)$ on the unit circle. The typical value at one point is $e^{O(\sqrt n)}$ and we need about $n$ points to read the true maximum (plus we have $n$ rows to serve), so my educated guess (which I can try to convert into a proof if this subexponential dependence is of any value for you) would be $e^{-\alpha \sqrt{n\log n}}$ with some $\alpha$ (with high probability; the expectation may be a bit larger because there is a chance that the rare large values will still dominate).
I hope it makes sense but I'm in quite a hurry right now, so accept my apologies if I said some nonsense somewhere.
