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?