I basically agree with you that supporting undelete is a lot friendlier to 95% or more of the population. But you can get the best of both worlds by simply keeping it around for a fixed time (and letting the user know how long after they hit delete) and then hard deleting. You can even offer them a "if you didn't mean to do that, click here; if you would like to permanently delete this now, click here"

You'll pay less for storage, too.