How to verify that method was NOT called in Moq?

Run a verify after the test with the Times.Never() option.

_mock.Object.DoSomething()
_mock.Verify(service => service.ShouldntBeCalled(), Times.Never());

UPDATE: Since version 3, check the update to the question above or Dann's answer below.

Either, make your mock strict so it will fail if you call a method for which you don't have an expect

new Mock<IMoq>(MockBehavior.Strict)

Or, if you want your mock to be loose, use the .Throws( Exception )

var m = new Mock<IMoq>(MockBehavior.Loose);
m.Expect(a => a.moo()).Throws(new Exception("Shouldn't be called."));

This does not work in recent versions of Moq (since at least 3.1), it should be specified in the Verify method as mentioned in the answer.

Actually, it's better to specify .AtMost(0) after the Returns statement.

var m = new Mock<ISomething>();
m.Expect(x => x.Forbidden()).Returns("foo").AtMost(0);

Although the "throws" also works, AtMost(0) is more expressive IMHO.

Stolen from: John Foster's answer to the question, "Need help to understand Moq better"

One of the things that you might want to test is that the pay method does not get called when a person aged over 65 is passed into the method

[Test]
public void Someone_over_65_does_not_pay_a_pension_contribution() {

    var mockPensionService = new Mock<IPensionService>();

    var person = new Person("test", 66);

    var calc = new PensionCalculator(mockPensionService.Object);

    calc.PayPensionContribution(person);

    mockPensionService.Verify(ps => ps.Pay(It.IsAny<decimal>()), Times.Never);
}