The two option solution is probably a good idea (perhaps naming it something like "destroy" because "delete" no longer has those kinds of connotation for many).

However, I would suggest penalising people genuinely concerned about their privacy and completely leaving out the option of permanent deletion, only because some people aren't responsible enough to to be trusted with that decision, is not really acceptable.