sed -i "/string1.*string2\|string2.*string1/d" input.txt
Isso excluirá qualquer linha onde string1 apareça antes de string2, OU string2 apareça antes de string1. Ambas as strings precisam estar na linha, em qualquer ordem, para que a linha seja excluída.