Cannot remove WorkItemHierarchy Link

I am attempting to move a milestone from one project to another via the API and I cannot remove the WorkItemHierarchy Link to the original project.  When I submit the deleteMessage I get a response that has Success = TRUE, which should indicate that the link was deleted (i.e. the delete message was processed), but when I look for the link, I find it still exists.  I actually create a new WorkItemHierarchy link before deleting the old one.  This then leaves two WorkItemHierarchy links with one child having two parents.