I believe the method you called to change the HTML text is pasteHTML(). If so, it is known issue but not fixed yet. The similar issue is reported to connect site at: http://connect.microsoft.com/VisualStudio/feedback/details/569921/ihtmltxtrange-pastehtml-method-does-not-replace-span-tags.
There is a work around you may try. The idea is that we can get the parent element of the selection if the text we selected contains the <a> tag, then we remove the this element directly. After that we insert the new html at this selection place using pasteHTML again. Here is the code:
//doc is a IHTMLDocument2 obejct.
IHTMLTxtRange range = doc.selection.createRange();
if (range.htmlText.Contains("A href"))
IHTMLDOMNode tempNode = range.parentElement() as IHTMLDOMNode;
Hope it helps.