I don't know how the redo add-on is made, but the right way to program a redo action in 'most' programs I'd imagine is to clear out all the redo actions once a change has been made.
Ex: User does 1, then 2, then 3
------*
1, 2, 3
user undos to 1
*
1, 2, 3
user does 4 now
---*
1, 4, 3
If the user redo's to action '3', it might cause corruption, because a change took place after the initial action, and action 3 could mean something completely different now that the changes took place.
I think how AGlassOfMilk (I think that's who made it) programmed the redo to just re-plant the brick after it's been removed, and in that case, the worst-case scenario is a floating brick or a brick inside another brick, if that.