Por que um funciona e o outro não?
SELECT REPLACE(N'IAșI' ,N'ș','x') -- doesn't match (returns 'IAșI')
SELECT REPLACE('IAșI' ,'ș','x') -- works (returns 'IAxI')
Meu palpite seria que, no segundo exemplo, o SQL Server vê 'ș' como 2 caracteres (0x19 02) e não faz algumas otimizações de agrupamento que arruínam a correspondência multibyte.
O que deve ser feito para que o exemplo multibyte funcione?
Não consigo explicar por que o primeiro não está funcionando (talvez alguma sutileza desse caractere Unicode específico). Isso produz um resultado bastante inesperado:
O segundo parecerá funcionar porque o SQL Server substitui caracteres multibyte por '?' ao lançar para varchar.
Este pequeno exemplo demonstra o comportamento, pois todos os argumentos serão convertidos em literais varchar:
EDIT : Parece estar relacionado ao agrupamento.