Eu tive esse problema no Open Office Calc (*. ods) (versão 4.0.1). O resultado ao procurar por uma string que eu pude ver claramente foi sempre "Chave de busca não encontrada". Resolvi quando percebi que havia marcado "células inteiras" em "Localizar e substituir" para um propósito específico e, depois, esqueci de desmarcá-lo.