When you remove a link between issues it only re-indexes the two issues if it was a system link (ie parent-> subtask), because these are the only links we store in Lucene index.
see DefaultIssueLinkManager.removeIssueLink()
On the other hand, when we create a new link, we always re-index, although it should probably only be necessary for system links.
see DefaultIssueLinkManager.createIssueLink()

Apparently Lucene indexing is a performance bottleneck.