A number of techniques are evolving, but the problem is still sufficiently cutting edge that the standardization process has not yet provided us with a totally portable solution.
Option one, you can make the web services transaction aware. This of course assumes you have control over them, although writing a transaction aware proxy for non-transactional services is also an option in some cases.
The WS-AT and WS-BA protocols are the leading standards for transactional web services. Unfortunately they specify the protocol only, not the language bindings. In other words, there is no standard API at the programming language level. For Java the nearest thing is JSR-156, but it's not ready yet.
Then the problem becomes: how to tie the EJB (i.e. JTA/XA) transaction to the WS one. Since the models used by the WS-AT and XA protocols are closely related, this can be achieved by means of a protocol bridge. Several app servers provide something alone these lines. JBoss presented theirs at JavaOne - see http://anonsvn.jboss.org/repos/labs/labs/jbosstm/workspace/jhalliday/txbridge/BOF-4182.odp
Note that the protocol bridging technique can also be used the other way around, to allow an EJB that uses e.g. an XA database backend, to be exposed as a transactional web service.
However, the locking model used by two phase commit transactions is really only suitable for short lived transactions in the same domain of control. If your services run in the same company datacenter you'll probably get away with it. For wider distribution, be it geographical or administrative, you probably want to look at WS-BA, a web service transactions protocol specifically designed for such use.
WS-BA uses a compensation based model that is harder to program. It's essentially based on the technique you mention: the effect of service methods is undone by calling a compensation method. This can be tricky to get right, but a JBoss intern did a rather nice annotation framework that allows you to define compensation methods with minimal effort and have them driven automatically. It's not standardized, but well worth checking out if you choose this approach: http://www.jboss.org/jbosstm/baframework/index.html