Yes, Ittai, I usually counsel against doing anything "always". For that reason, I (usually) advise people to "mock Services freely", meaning "don't feel any guilt when mocking a Service".
On the other hand, I often advise people "mock all Services for the next four weeks" as a form of deliberate practice. Sometimes the only way to find the edge of the cliff is to fall over it a few times. Once you've mocked a lot of Services you'll feel more able to judge when to do it and when not to. This relates to the "peers v. internals" notion in Growing Object-Oriented Software Guided by Tests.
Often we end up with small clusters of objects that work together to expose a single component API. I might and might not find myself separating those objects from each other by interfaces. As always, it depends. Often if I do separate those objects by interfaces, then I discover that part of the component stabilises and becomes more widely reusable and the rest becomes a plugin/policy/strategy.
As you point out, I mock Services in order to find the essential interactions between modules. We could do that other ways, but I find mocking Services especially effective at doing that.