This question highlights important differences between appropriate uses of exception handling, transactions, and the idea workflow "compensation" which is what the asker is trying to get at, when correctly stating:
This seems like a type of problem that would occur in many applications and there should be a clean way to handle it.
It is a common problem, first some background on the transactional approach you are currently attempting:
Data transactions were originally modeled after double-entry accounting -- a single credit and a corresponding debit had to be recorded together or not at all. As transactions get bigger than this they become increasingly problematic to implement correctly, and harder to deal with a failure. As you start to carry the idea of a single transaction across system boundaries, you are most likely approaching it wrong. It can be done, but requires complex and necessarily higher-latency transaction coordinators. At a certain scale transactions are the wrong mindset, and compensation starts to make a lot more sense.
This is where you go back and look at what the business actually does. A single large transaction is most likely not the way the business people see it. Usually they see a step completed, and depending on subsequent results, different actions to compensate may be needed. This is where the idea of a workflow and compensation comes in. Here's one introduction to those concepts
For example if you order a book from Amazon, they probably don't "lock" the record while it is in your shopping cart, or even use strict transactions to determine if the book is still in-stock when the order is confirmed. They will sell it to you anyways, and ship it when they can. If they haven't managed to get it in-stock within a few weeks they will probably send you an email telling you that they are trying to meet your needs, and you can keep waiting for them to get it in-stock, or you can cancel your order. This is called compensating, and is necessary in many real-world business processes.
Finally, there is nothing exceptional about any of this. Expect that this can happen and use normal control flow. You should not use your language's exception handling features here (good rules for when to throw an exception). Nor should you rely on tool specific (WCF?) mechanisms for seeing or handling exceptions that happen within the service implementation. Communicating faults should be a normal part of your data contract (fault contracts).
Unfortunately, by "clean way to handle it" there is no flag to set that will magically take care of it, you have to continue to decompose the problem and deal with all the resulting pieces. Hopefully these concepts will connect you with what other people have done when dealing with this issue.
Summary:
- Your problem has outgrown the concept of a transaction --> look into workflow compensation.
Good luck -