Sed é muito ruim nisso, porque opera uma linha por vez. A única técnica decente que eu já vi para fazer isso é este aqui , que envolve armazenar todo o arquivo no buffer de espera do sed e depois operá-lo de uma vez:
sed -n '1h;1!H;${g;s/search/replace/;p;}'
Se você puder, é muito mais fácil usar o perl para fazer isso:
perl -0pe 's/search/replace/'
search
pode conter \n
s para representar novas linhas