I like the approach of each DUP being responsible for cleaning itself up if it fails, with the cleanup call being reserved for those that had previously completed successfully. That's the way the handling of lists of model/runtime updates work.
Putting the logic to do the cleanup work inside DeploymentChain.processDeployment() seems easiest -- no need to do any kind of external bookkeeping of what DUPs have been invoked and need cleanup. The contract for that method can guarantee that all cleanup will be done before any exception is thrown.