Mt.Gox introduced verification not so long ago (in May 2013, IIRC). That was supposedly done to increase safety of withdrawals, although at a cost of reduced privacy. I am certainly not comfortable with sending Mt. Gox my ID and/or utility bills, although others may have other opinion on that.

Mt.Gox isn't the only exchange, there are others with less privacy-invading practices.