While I agree that most current shared hosting solutions offer non-SUPER MySQL 5.0, I do think that this is temporary; our stats show that 16% of CiviCRM installs are already using MySQL 5.1, and this percentage has been growing steadily in the past year. Doing this kind of thing on the PHP side (rather than with triggers) would be IMHO both very error-prone and inefficient, not to mention not easily scalable across tables.

As for the undelete vs. logging split – I agree that logging could provide undelete, but I’d rather not couple them too tightly unless its either necessary or very beneficial. First, we need undelete sooner than logging (and it’s easier to implement); second, they serve different purposes and have different target audience – undelete should be usable by anyone with edit/delete permissions, while logging/revisioning should be more tailored towards admins (but perhaps to be usable as a historical view by ‘regular’ users with a separate permission for this).

I agree that at some point we might want to offer the ‘bringing back’ of any past state of a contact, but I doubt it’s trivial (and so I doubt this is doable for CiviCRM 3.2); also, if we do end up doing that and it turns out to cover undelete without cluttering the UI/workflows, we can easily retire undelete at that time.

Finally, I agree we should think deep about our designs, but this is also the reason why I much rather see this kind of functionality as decoupled from other things as possible (and transparent to these parts of CiviCRM that shouldn’t be bothered whether there’s any undelete and/or logging functionality at all).