>The reindexing routine deletes all tags and starts from scratch at the user and at my site, so that wasn't the issue

Then, I would look for interrupted service or related. If this is freshly indexed, then there could be severe crashes at the client site that could cause this.