Hmm, do you have some example of these dangerous scenarios? I suspect a lot of tools have come to think of the "file path" as the identifier for a file. So of course they would break if that classification were to be reorganized, like if two parent categories were to swap. I would call that an abuse of the file system though. But the status quo is what it is. Most file systems already have lots of other metadata built in that can be used to access the inode or whatever you call your data structure. My point is, accessing data in a more general case is a search operation.

As far as an external tag store, that is basically what a search index is. And Recoll is full-text, so each file has a shit-ton of tags associated with it. You then just pass the -m flag to the indexer, and it monitors for file modifications, and updates the index accordingly. I have not noticed a significant performance impact there. Mostly just the initial index operation sucks.