said by donoreo:
Could be. I do not have it enabled and mine works.
Based on what? Please don't speculate, that doesn't help with the OPs issue at all. I have 2 step authentication turned on and it hasn't caused a problem for me at all. OP, what mail clients are you using? And are there more clients than just the phone and the Mac? Some clients, even when set up as IMAP, will delete messages from the server, although I don't think this is the behavior of the the default iPhone app or Mountain Lion mail.app.