A planned, forthcoming improvement to the above NOT_MY_VBUCKET handling approach is that Couchbase will soon send an optional second map during the start of the Rebalance. This second map, called a "fast forward map", provides the final vBucket-to-server map that would represent the cluster at the end of the Rebalance. A client library can use the optional fast forward map during NOT_MY_VBUCKET errors to avoid linear probing of all servers and can instead just jump straight to talking with the eventual vBucket owner.
Please see the implementation in libvBucket that handles a fast-forward-map here.
The linear probing, however, should be retained by client library implementations as a good fallback, just-in-case error handling codepath.