I just discovered that you can add the --precise flag when using wp search-replace with WP-CLI.

I’ve never needed to use this before, so I wouldn’t suggest using it by default, but I had a site that was stubbornly refusing to replace all instances of a test domain after switching to the production domain and this solved it.