This implementation is better in terms of polymorphism (nice work!) but it creates an excessive number of objects -- which in turn need to be GC'd.  Consider an expression like `receive_message_chain(:foo, :bar, :bazz)`.  Here's the objects this will create:

* `stub_chain_on` is called, which creates an instance of `StubChain` and calls `stub_chain` on it.
* In `stub_chain`, it creates an instance of `AllowChainStrategy` and calls `walk_chain`.
* That in turn calls `AllowChainStrategy#chain_on`, which turns around and calls `stub_chain_on`, which creates another instance of `StubChain` and repeats the process with one less message in the chain.

There's also the test doubles that get created (but those have to be created).

The number of throw-away objects involved in this process scales linearly with the number of messages in the chain.

I think there's a better way to do this that will involve much fewer object instantiations (which should perform better) and be easier to maintain, to boot:

* Split this up in to two classes: `StubChain` and `ExpectChain`.
* Have the recursion recurse onto itself rather than creating a new instance to recurse onto.
* With this setup, there won't be a need for separate strategy classes--`StubChain` and `ExpectChain` will basically implement those strategies within themselves.
* They can share a base class if there's any common logic.  (Basically, this would be an implementation of the template method pattern if you're familiar with that term).
* If you like, the main entry point method can be named the same (something like `setup_chain_on`), and from the `receive_message_chain` matcher it can either call `StubChain.setup_chain_on(...)` or `ExpectChain.setup_chain_on(...)` appropriately.

Let me know if that makes sense.