I think it's still useful to have a sentence explaining the requirements for spying.  Maybe something like this:

``` ruby
For a message to be verified, the given object must be setup to spy on it, either by having it explicitly stubbed or by being defined as a `spy`.
```