I've to seriously reconsider the use of soft-deletes (as these are called) and to not use them. The working set you'll work with is, over time, much smaller than the real # of rows in the db, which has issues on its own.
You should implement a delete trigger which copies the rows to an archive table, and an undelete should simply re-insert the entities. You can also circumvent this in the GUI, as deleting information is often not necessary, and IF people want to delete information, it is REALLY GONE. Why not simply leave the data there? And if you want to get rid of it, because it pollutes the workingset, ARCHIVE it. Because that's what you want: you want to delete the info, but in case some moron hits delete accidently and you want to get it back, it's not completely gone.
Repaving my windows partition also wipes everything clean, there's no undo option once I've formatted an fdisk-ed hdd.