I have the following interface that I want to mock:

public interface ISomeInterface
{
    string GiveMe(Expression<Func<Person, bool>> predicate);
}

With the following Poco:

public class Person
{
    public string Name { get; set; }
}

Then I am setting up my mock as:

[Test]
public void Run()
{
    var expectedPredicate = It.IsAny<Expression<Func<Person, bool>>>();
    var mock = new Mock<ISomeInterface>(MockBehavior.Strict);
    mock
        .Setup(m => m.GiveMe(expectedPredicate))
        .Returns("Yo!");

    var message = mock.Object.GiveMe(p => p.Name == string.Empty); // throws
}

But I am getting:

Invocation failed with mock behavior Strict. All invocations on the mock must have a corresponding setup.

What am I missing here?