My understanding is that you don't destroy the information, you copy the relevant parts and then reverse the original computation. More specifically you only copy the parts of the computation that are relevant to you, you don't copy the entire (much larger) intermediate state.
So you are only ever doing truly destructive operations on a small buffer at the beginning and end of each each "clock cycle" instead of for every logic operation.
Alternatively a fully-reversible circuit could look more like a mechanical clock, you can return it to any state just by moving the key backwards/forwards far enough. It gets more complicated when you start including any kind of IO, but in theory you'd still only be copying/overwriting bits every so often, with a normal circuit being cyclical.