Assuming you verify users over the phone securely, why not just reset their passwords for them with a one-time use, temporary password? Surely that's not much harder for the end-user to deal with, and then you needn't store their password...