Na minha opinião a idéia está certa, porém, acredito que o seu regex não esteja adequado.
Lhe indico este site: http://regexlib.com , muito bom para conseguir expressoes regulares de qualidade, com certeza voce vai encontrar uma que faça isso que voce quer, dai é só substituir por string vazia mesmo.
O replace faz uma varredura caracter por caracter do inicio para o fim. Dai ele substitui tudo pelo fazio.
O replaceAll pode ter problemas com caracteres como ($)
replaceAll
* Note that backslashes (</tt>) and dollar signs ($) in the
* replacement string may cause the results to be different than if it were
* being treated as a literal replacement string; see
* {@link java.util.regex.Matcher#replaceAll Matcher.replaceAll}.
* Use {@link java.util.regex.Matcher#quoteReplacement} to suppress the special
* meaning of these characters, if desired.
replace
* Replaces each substring of this string that matches the literal target
* sequence with the specified literal replacement sequence. The
* replacement proceeds from the beginning of the string to the end, for
* example, replacing “aa” with “b” in the string “aaa” will result in
* “ba” rather than “ab”.