For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$? Is it guaranteed that there will be some $p$ such that  $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$?
In other words, does each $2^x-1$ introduce a new prime factor?

Yes, it's true (except for $2^6-1=7\times 9$).
This is known as Bang's theorem, and is a corollary of Zsigmondy's Theorem.
You can find a proof here (Theorem 3).
