SOME multibyte encodings can safely be used in str_replace() and the like, others cannot. It's not enough to ensure that all the strings involved use the same encoding: obviously they have to, but it's not enough. It has to be the right sort of encoding.
UTF-8 is one of the safe ones, because it was designed to be unambiguous about where each encoded character begins and ends in the string of bytes that makes up the encoded text. Some encodings are not safe: the last bytes of one character in a text followed by the first bytes of the next character may together make a valid character. str_replace() knows nothing about "characters", "character encodings" or "encoded text". It only knows about the string of bytes. To str_replace(), two adjacent characters with two-byte encodings just looks like a sequence of four bytes and it's not going to know it shouldn't try to match the middle two bytes.
While real-world examples can be found of str_replace() mangling text, it can be illustrated by using the HTML-ENTITIES encoding. It's not one of the safe ones. All of the strings being passed to str_replace() are valid HTML-ENTITIES-encoded text so the "all inputs use the same encoding" rule is satisfied.
The text is "x<y". It is represented by the byte string [78 26 6c 74 3b 79]. Note that the text has three characters, but the string has six bytes.
<?php
$string = 'x<y';
mb_internal_encoding('HTML-ENTITIES');
echo "Text length: ", mb_strlen($string), "\tString length: ", strlen($string), " ... ", $string, "\n";
$newstring = str_replace('l', 'g', $string);
echo "Text length: ", mb_strlen($newstring), "\tString length: ", strlen($newstring), " ... ", $newstring, "\n";
$newstring = str_replace(';', ':', $string);
echo "Text length: ", mb_strlen($newstring), "\tString length: ", strlen($newstring), " ... ", $newstring, "\n";
?>
Even though neither 'l' nor ';' appear in the text "x<y", str_replace() still found and changed bytes. In one case, it changed the text to "x>y" and in the other it broke the encoding completely.
One more reason to use UTF-8 if you can, I guess.