It's not a nightmare unless you try to tack it on after the fact. Start (or earlier in the process incorporate) some variation of command pattern into the system and it's not too bad. Some actions will remain irreversible, but those are ones that would be irreversible regardless of whether you have an undo-facility or not.
Right, something like a transaction log is extremely useful in many circumstances, it's just a smart way to build stuff. It can give you better data integrity, sane parallel processing, etc.