If you're willing to work with me, we can try to debug this.
1) Rebuild your workspace tag file from scratch. (Project > Retag Workspace...)
2) Then exit the editor and make a backup of that workspace tag file.
3) Now turn on the following macro variable to enable logging (Macro > Set Variable... > def_tagging_logging=1). As soon as you encounter one of the problems, note the file's involved, and capture <config>/logs/tagging.log.
4) Exit the editor again and make a copy of the workspace tag file in it's current state (where you are getting failures).
5) Turn def_tagging_logging back off and rebuild your tag file.
Send me the original tag file, the current tag file, tagging.log, and notes about what files and symbols were involved with the failed searches. I can look over all this data and see if I can identify the problem. The caveat is that I need all the data, otherwise, I won't be able to determine what is missing from the tag file when it is failing.