I'm using Tangible as integrated into the LiveCanvas plugin. When I have the LiveCanvas plugin enabled, WP-cli's "search-replace" function does not update the URLs in the wp_options table and potentially, other tables.
We tracked the issue to Tangible. In the LiveCanvas plugin, if we disable tangible, WP search-replace works correctly.
I worked with Jeff at LiveCanvas first, but he said the issue isn't with the LC implementation, but with Tangible itself. He advised me to open up an issue with Tangible.
Edit -- more context: taking Live Canvas out of the equation by disabling the plugin and enabling the Loops and Logic plugin also caused the same issue.