To improve search results internal on the site, including the tag links, I have just started re-indexing the search database for the whole site.
This is done by resetting (deleting) the current search database. And with almost 200000 posts, this is not done in an hour or two. I estimate that it will take 2-3 days before everything is re-indexed. So the best time is over a weekend.
I will post an update to this post, when the indexing has been completed.
Forgot to post the update. All posts have now been reindexed.