If I understand correctly, the triggers approach for undelete will require Super privileges and therefore not work in a shared hosting environment. I would strongly suggest you consider that as criteria. Civi is targeting non-profits who often need to start (or stay) with shared hosting. Of course you might disable that feature for shared environments (reasonable) but if there is a way to avoid it, you should consider that.
Perhaps an naivete question but if logging might use mirrored (relevant) tables, why not undelete also? Effectively, deletes would be "moves" to another database. Defintely not performance friendly, but you could keep a separate database for logging, undelete or other "future" meta information about each transaction .... just a wild thought.

Finally, whatever the "solution" please consider the that if civi maintains its growth rate, it will likely be a much more ubiquitous tool in the near future. While views might make legacy code more manageable, please make sure you build a solid architecture for the future.

Great thinking and excellent post!

Shawn