Revisa tildes (si no has marcado la opción de diacríticos), espacios, mayúsculas (por si has seleccionado una opción de coincidencia) del texto buscado. Sino consulta la
ayuda
Yo la búsqueda la uso mucho y no tengo problemas. Uso sobre todo la opción de buscar y reemplazar siguiente pero reemplazar todos nunca me ha dado problemas.
También puede ser un problema de codificación de caracteres pero sería raro, suele suceder al subir textos que se han modificado en muchos equipos diferentes, con distintos programas... Ahí te recomiendo bajar el texto, borrarlo del servidor, cambiar de codificación y volver a subir.
Si tienes que sustituir un texto mal escrito, pero que puede tener variaciones deberás usar las expresiones regulares ya que solo detecta textos exactos: un solo espacio en blanco de más y falla.