I believe that society would probably be a tad bit more calmer, but out of fear than anything. People would still steal and commit crimes, and a lot of them would be killed. That way the society could easily understand that the person who "deleted" the attacker, robber, rapist or whatever was the same victim. It could be punishable or not, but it would depend on how serious the society, that has seen hence deletion happen a lot (because I believe that some people would abuse this, even if it's a 1 in a lifetime, like we do with most things) would treat that self-protection out of the deletion.
But yes, crimes would still happen. They'll always happen. They'll just have to be more hidden, from away. I don't know how crime would be like because I don't really know how far does the "deletion ability" needs to know about the user, like think of his traces or just know his name or simply know that he's there. But it'd be less existent out of fear, but of course, still happens.