A maioria dos comandos que enviam dados no stdout (que inclui grep e sed ) armazenam em buffer sua saída quando não estão indo para um terminal. Ou seja, eles esperam por um grande pedaço de saída para se reunir (como 4KiB) antes de liberar o pedaço para o arquivo ou pipe. Isso geralmente é mais eficiente. Alguns comandos permitem que você sobrescreva isso, como o GNU grep , que possui uma opção --line-buffered , e o GNU sed tem uma opção --unbuffered . Para comandos que não têm como substituir o buffer, você pode usar ferramentas como unbuffer ou stdbuf .
Nesse caso, eu consideraria usar GNU awk , onde você pode controlar o fluxo de stdout (com a função fflush).
tail -f file | gawk '/string/{ gsub(/stuff/, "") } { print; fflush() }' > output.txt
Veja BashFAQ # 9 para mais informações sobre armazenamento em buffer.