Moq: Setup a mocked method to fail on the first call, succeed on the second

What's the most succinct way to use Moq to mock a method that will throw an exception the first time it is called, then succeed the second time it is called?

I would make use of Callback and increment a counter to determine whether or not to throw an exception from Callback.

[Test]
public void TestMe()
{
    var count = 0;
    var mock = new Mock<IMyClass>();
    mock.Setup(a => a.MyMethod()).Callback(() =>
        {
            count++;
            if(count == 1)
                throw new ApplicationException();
        });
    Assert.Throws(typeof(ApplicationException), () => mock.Object.MyMethod());
    Assert.DoesNotThrow(() => mock.Object.MyMethod());
}

public interface IMyClass
{
    void MyMethod();
}

Starting with Moq 4.2 you can just use the built-in method SetupSequence() (as stated by @RichardBarnett comment).

Example:

var mock = new Mock<IMyClass>();
mock.SetupSequence(x => x.MyMethod("param1"))
    .Throws<MyException>()
    .Returns("test return");

The best that I've come up with so far is this:

interface IFoo
{
    void Bar();
}

[Test]
public void TestBarExceptionThenSuccess()
{
    var repository = new MockRepository(MockBehavior.Default);
    var mock = repository.Create<IFoo>();

    mock.Setup(m => m.Bar()).
        Callback(() => mock.Setup(m => m.Bar())). // Setup() replaces the initial one
        Throws<Exception>();                      // throw an exception the first time
    
    ...
}

Phil Haack has an interesting blog post on setting up a method to return a particular sequence of results. It seems that it would be a good starting point, with some work involved, because instead of a sequence of values of a certain type, you would need now to have a sequence of results which could be of type T, or an exception.