So, depending on the need, I will either have two directories (files and tags) or a number of file directories and a tag directory. File directories can have whatever they want, and tag directories have either only tag directories (like workout, driving, etc) or soft links.
Tagging a file / directory is easy - just link to it. Untagging is just as easy. The links don't take up much space, especially next to the music. When I'm transferring the files, I either use a script to make a directory with the links replaced with their file counterparts, or I transfer with something like rsync that can do that itself.
I'm amazed how similar this project is to my own solution. It's nice to have a dedicated script for the whole thing, but the solution itself is very simple, and easy to script with.
This isn't born out of frustration - hierarchical filesystems are perfectly adequate for most tasks. But they have not been trees for a long time - we have links, which let us make any graph we want out of those trees.