In TDD, I'm going to test units together when it makes sense. They way I see it, I use mock/stubs for two reasons: the behavior of the system becomes too complex to effectively test with the full implementation, and the full implementation may do things I don't want to happen.
Basically, the more objects are involved in a test, the more difficult the system will be to predict. You've got the predict the behavior of the system in order to write the test. Some object may have complex behavior and it may be difficult induce particular edge cases in one unit. Thus it can be really helpful to mock those objects.
In other cases, the objects have side effects that are undesirable. Suppose you have a CreditCardProcessor. You don't really want to charge credit cards while your tests are running. Other items like drawing graphics or accessing web resources may be in the same category.
When an object has a dependency, how do you decide whether to include the actual object or some sort of mock/stub?
Firstly, if there is any possibility that the behavior of the object will change during development I'd stub it. For example, consider a priority queue class vs a price strategy class. A priority queue will almost certainly always maintain the same behavior. However, your pricing strategy is likely to change a lot. As a result, you don't want other tests to depend on the behavior inside pricing strategy. If they do, you'll just end up breaking other tests needlessly. However, its not really a big deal for priority queue because the behavior should never change.
Secondly, how "fat" is the interface between the objects? If the objects have a very simple interface, then mocking is easy and I'll do it. If the objects have a complex interface then mocking is hard and less likely to be worthwhile. In this case, let's contrast a database connection object and a price strategy. The price strategies interface should be reasonably simple, hopefully just a CalculatePrice(SalesOrderItem) method. Sure, the actual code may do all sorts of things with the SalesOrderItem, but your stub doesn't have to deal with that. On the other hand, a database connection has SQL statements being passed to it which gives it a fairly complex interface. Mocking the database is really hard because you have check all of the queries that are being made and provide correct response. Furthermore, you aren't checking to make sure that the queries are valid (just that they match what you expect), in such cases checking against an actual database makes more sense, that way you actually verify that the queries work and the tests will still pass if you rewrite the queries to give the same results but in a different way.
Thirdly, if an object will be slow I stub it. If you have a database, calls to it will be fairly slow prompting the use of a stub to avoid having to call into it. Similar for web access, etc.
I did just use databases as an example of something you should stub and also not stub. I stub my databases with a sqlite in-memory database which avoids the performance problem but still allows my SQL to be tested. I'm actually using a framework that generates SQL specific to my database for me so that's work.
In your actual case, you state:
The majority of our unit tests are behavioural tests which often became false negative (false red) during refactoring (just because some sequence of dependencies calls changed).
As I understand this, your tests fail because before foo() was called first then bar(). Now bar() is called then foo(). If the order of calling foo() and bar() doesn't matter, your tests shouldn't be checking which called first. Your test should only be verifying that both are called.
