Почему бы не попытаться избежать квантора? htmlString.replaceAll("<\\S*?>", "")
htmlString.replaceAll("<\\S*?>", "")
(Это Java, но главное - показать идею)