We show that exact recovery in the noisy Matrix Completion problem can be achieved under the basic assumptions without the need for a small condition number or large singular value gaps, using novel techniques that can be of independent interest.