Have you verified that nothing has clogged the fins above the vapor chamber? If some dust got in there, it could definitely cause issues.
If you have verified, and you have redone the paste, then it may be a different issue completely.
This may be a silly question, but have you looked at the fan while it was on to make sure the fan is actively spinning?