wp cache flush can fail when the cache holds a stale domain lookup value and DOMAIN_CURRENT_SITE is properly set to the new domain (previously wp-cli/search-replace-command#12):

$ wp cache flush
Error: Site 'mstest.org/' not found. Verify DOMAIN_CURRENT_SITE matches an existing site or use `--url=<url>` to override.
$ wp config get --constant=DOMAIN_CURRENT_SITE
mstest.org
$ wp db query "SELECT domain FROM wp_blogs"
+------------+
| domain     |
+------------+
| mstest.org |
| mstest.org |
+------------+

It shouldn't need to be this way! wp_cache_flush() has no dependency on the site context. It should be possible to call it before multisite context has been bootstrapped. However, there's no pragmatic way to do so currently:

Once we sort this out and the problem is solved, we should remove the message in wp search-replace too.