Should you use the "Verify" and "VerifyAll" methods provided by Moq in your Unit Tests?

It seems like using them as a method to ascertain whether the method under test executed properly is counterproductive because it will lead to brittle tests. In other words you're tying the test to the implementation. So if you later want to change the implementation you're also going to have to change the test. I'm asking this question because I was trained to always use at least one of these methods in every unit test and I think I may have just had an epiphany that this is actually a very bad practice.