Compromise: first time recovery is free, every subsequent time requires a 99¢ fee.

That way it still discourages people wantonly deleting characters, but allows people to change their minds after the fact, if they so choose.

The other option would be to allow for "retirement" for characters. You can't log into them, and they aren't in active memory on the servers, but they can be "come out of retirement" with relative ease, and without having to pay (in this situation, set a limit on the number of retired characters a player can have, and limits on how frequently players can retire and revive characters).