Просто помните, что PHP str_replace будет заменять слева направо.
В этом случае это просто вопрос сортировки массива исходных значений в порядке убывания, например, так: «ss» встречается до «s» (в противном случае «ss» будет заменено на «àµƒàµƒ» вместо «àµˆ»).
$original = array("€", "Å“", "Å’", "ž", "Ž", "Ÿ", "Å¡", "Å ", "Ù", "À", "Û", "Ë", "É", "Ã…", "Õ", "Ç", "Æ", "Ä", "Ô", "Ó", "Â", "Ã’", "Ñ", "×", "Ö", "Ø", "È", "Ã", "Þ", "ÃŽ", "ß", "Ú", "Ê", "Ãœ", "ÃŒ", "þ", "õ", "ô", "ó", "ò", "ñ", "ð", "ï", "î", "Ã¥", "ä", "ã", "â", "á", "à ", "Ã", "Ã", "Ã", "Ã", "Ã", "¿", "¾", "½", "¼", "»", "º", "¹", "¸", "·", "¶", "µ", "´", "³", "²", "±", "°", "¯", "®", "¬", "«", "ª", "©", "¨", "§", "¦", "Â¥", "¤", "£", "¢", "¡", "Â", "}", "|", "{", "z", "y", "x", "w", "v", "u", "tm", "t", "su", "ss", "sm", "sF", "s", "r", "q", "p", "o", "n", "m", "l", "k", "j", "i", "h", "g", "f", "e", "d", "c", "b", "a", "`", "_", "^", "]", "\p", "\", "[", "Z", "Y", "X", "W", "V", "U", "T", "S", "R", "Q", "P", "O", "N", "M", "L", "K", "J", "I", "Hu", "Hm", "H", "G", "F", "E", "Du", "D", "Cu", "C", "B", "A", "$");
$replaced = array("à´—àµà´—", "à´®àµà´®", "à´®àµà´ª", "à´ªàµà´ª", "à´¨àµà´¤", "à´®àµà´²", "à´šàµà´š", "à´™àµà´•", "à´¸àµà´¥", "à´¨àµà´¦", "à´¤àµà´", "à´¹àµà´²", "à´³àµà´³", "à´®àµà´®", "à´žàµà´š", "à´¯àµà´¯", "à´µàµà´µ", "à´®àµà´ª", "à´¨àµà´§", "à´¹àµà´¨", "à´¨àµà´±", "à´¹àµà´®", "à´šàµà´›", "à´£àµà´®", "à´œàµà´œ", "à´¸àµà´¥", "à´²àµà´²", "à´ªàµà´ª", "à´£àµà´¡", "à´•àµà´Ÿ", "à´¤àµà´®", "à´œàµà´ž", "à´±àµà´±", "à´—àµà´®", "à´±àµà´±", "-", "à´", "à´¸àµà´¸", "à´¨àµà´¨", "à´¨àµà´®", "à´²àµà´²", "à´²àµâ€", "à´¨àµà´®", "à´¨àµ", "à´±àµà´±", "à´·àµà´Ÿ", "à´¨àµà´±", "à´—àµà´¨", "à´£àµà´Ÿ", "à´•àµà´¤", "à´¶àµà´š", "à´¨àµà´¤", "à´¬àµà´§", "à´¡àµà´¡", "à´¨àµà´¨", "à´¤àµà´¤", "à´£àµà´Ÿ", "à´Ÿàµà´Ÿ", "à´žàµà´ž", "à´šàµà´š", "à´™àµà´™", "à´™àµà´•", "à´•àµà´·", "à´¨àµà´®", "à´¨àµà´¨", "à´¨àµà´¦", "à´¨àµà´¤", "à´³àµâ€", "à´²àµâ€", "à´°àµâ€", "à´¨àµâ€", "à´¤àµà´¤", "à´£àµà´£", "à´£àµà´Ÿ", "à´£àµâ€", "à´Ÿàµà´Ÿ", "à´¦àµà´§", "à´žàµà´š", "à´“", "à´™àµà´™", "à´™àµà´•", "à´¦àµà´¦", "à´ˆ", "à´•àµà´·", "à´•àµà´²", "à´•àµà´•", "àµà´°", "àµà´µ", "àµà´°", "àµà´µ", "àµà´¯", "à´ƒ", "à´‚", "ൌ", "േ", "ോ", "െ", "ൌ", "ൈ", "ൊ", "à´", "ൃ", "ൂ", "àµ", "ീ", "à´¿", "à´¾", "àµ", "à´±", "à´´", "à´³", "à´¹", "à´¸", "à´·", "à´¶", "à´µ", "à´²", "à´°", "à´¯", "à´®", "à´", "à´¬", "à´«", "à´ª", "à´Œ", "à´¨", "à´§", "à´¦", "à´¥", "à´¤", "à´£", "à´¢", "à´¡", "à´ ", "à´Ÿ", "à´ž", "à´", "à´œ", "à´›", "à´š", "à´™", "à´˜", "à´—", "à´–", "à´•", "à´”", "à´“", "à´’", "à´", "à´Ž", "à´‹", "à´Š", "à´‰", "à´ˆ", "à´‡", "à´†", "à´…", "à´¸àµà´±àµà´±");
$new_string = str_replace($original, $replaced, $old_string);
Примечание: кодировка должна быть windows-1252, а не UTF-8, так как str_replace с массивами непредсказуемо с многобайтовыми заменами.