I've encountered a situation where due to some other area of code I called failing to copy a Dictionary<TKey, TValue> that it returns, a concurrency problem ensues: the Dictionary appears to contain illegal null keys.
I've fixed the underlying bug, but to help identify this issue should it crop up again in the future I'm adding a bit of code that explicitly checks for the null key in the loop that processes the returned dictionary and throws before things go any further. I'm not sure which exception class to throw, or which one to subclass if I'm defining a new one.
Does any caller expect the exception? Can any caller handle the exception? Can any caller recover from the exception? What do you imagine is going to happen after the throw?
In this situation where data structures are arbitrarily corrupted pretty much none of your invariants are known to be true. The fact that you're still running code at all is a miracle. Unless you have a good reason to do otherwise I'd be inclined to log any info necessary to diagnose the bug and fail fast. Throwing an exception and running finally blocks is unlikely to make anything better.
Ultimately of course anything you do is a stopgap. Fix the bug that is corrupting your data.