A "true rollback" (which as I said isn't being used by an major RBDMS that I am aware of) would actually be much faster than any other method (i.e. you either are going to have to issue update queries to act as though things are being unwound or restore an earlier backup which you'd then have to perform a partial log restore from).

Understand also that even if deletes involve appending the data to the log you would still be able to truncate the log for "checkpoints" (at which point any of that extra wasted space is recovered).