Você pode ter mais sorte usando o perl, que é compatível com a correspondência literal de strings por meio do modificador \Q
(frase citada), por exemplo.
perl -pe 's/\Qstring/replacement/g'
Veja, por exemplo, este artigo Sintaxe de expressão regular Perl em boost.org