bueno que yo sepa str_replace no es sensible a mayusculas y minusculas...
Lo más probable es que si buscas en una base de datos, estes buscando en campos de tipo BLOB o algo asi, que son sensibles a mayusculas. Si queres evitar esto tenes que usar por ej TEXT en vez de BLOB...
Si en cambio buscas en un archivo determinado, te recomiendo que usando strtolower pases la string a buscar, y el texto en que buscas enteramente a minusculas..
Saludos
<div align="center"><img src="http://cablemodem.fibertel.com.ar/sainztrapaga/images/firma.jpg" width="435" height="70" border="0">
</div>