An all too real threat to the privacy offered by a mix network is that individual mix administrators may volunteer partial tracing information to a coercer. While this threat can never be eliminated - coerced mix servers could simply be forced to reveal all their secret data - we can deter administrators from succumbing to coercive attacks by raising the stakes. We introduce the notion of a trace-deterring mix permutation to guarantee privacy, and show how it ensures that a collateral key (used for an arbitrary purpose) be automatically revealed given any end-to-end trace from input to output elements. However, no keying material is revealed to a party who simply knows what input element corresponds to what output element. Our techniques are sufficiently efficient to be deployed in large-scale elections, thereby providing a sort of publicly verifiable privacy guarantee. Their impact on the size of the anonymity set - while quantifiable - are not of practical concern.