The best solution doesn't need anything, e.g. if we have calls to our persistence layer mixed in with calculations, the latter shouldn't be tested with fakes/mocks; instead we should refactor the code so the calculations don't depend on the persistence layer.
If the behaviour of some code depends inextricably on some external system, then our tests should use that system. This avoids unnecessary code/work/duplication, allows tests to exercise more paths through our codebase, exposes problems in our understanding of that system, etc.
If calling an external system in our tests is dangerous, unacceptably slow, costly (if it's some Web service), etc. then we should make a fake implementation to test against. If our code only uses a small part of some large, complicated dependency, we might want to define an interface for the subset that we need, refactor our code to use that, and only have our fake implement that part.
If a fake implementation isn't practical, or would require so much overriding per-test as to be useless on its own, then I might consider using mocks. I would seriously consider whether that code could be refactored to avoid such coupling. I would also never make assertions about irrelevant details, like whether a particular method was called, or what order things are run in.