trace ni zorra de php pero str_replace suele tener 3 parametros:
A) la cadena que contiene el texto.
B) la cadena a buscar.
C) la cadena que se pondrá en lugar de la que se busca.
Así a bote pronto se me ocurre esto:
En la función debes hacer lo siguiente:
1) Pasar A y B a grandúsculas (AA y BB)
2) Buscar el indice del primer caracter de BB en AA (POSSTART) y también el último (POSEND).
3) Obtener una cadena A1 que contenga los caracteres de A desde el cero a POSSTART.
4) Obtener una cadena A2 que contenga los caracteres de A desde POSEND hasta la longitud de A.
5) devolver A1 + C + A2
yasta 
así en seudotolecodigo seria:
funcion str_replaceNOCASE(string cadena, string ocurrencia, string nueva)
InicioFuncion
string cadenaMayus = UpperCase(cadena);
string ocurrenciaMayus = UpperCase(ocurrencia);
int inicio = Posicion(ocurrenciaMayus, CadenaMayus);
int fin = inicio + Length(ocurrencia) – 1;
string inicioCadena = Left(cadena, inicio);
string finCadena = Right(cadena, Length(cadena) – fin);
resultadoFuncion = inicioCadena + nueva + finCadena;
FinFuncion;
Bueno no se si me he equivocao
, espero que no.

