The hard link solution has indeed advantages, but its limit is really a bad one. I have my files spread on about 3 Harddisks, all in my home dir.
Could the filesystem interface not treat cp's as symbolic links, not copying the file, but just creating a symlink? Additionally, instead of creating a simlink you could save the full path in the database and create the sym..or hardlinks on the fly. As in, when the user types ls, it creates the content from the database.
The problem here is of course, the moving and deletion of files. But there is a nice library for that out there: inotify see
http://inotify.aiken.cz/?section=incron&page=about&lang=en . You can watch whole directory structures for changes of any kind with that. You could even attach certain tags to certain directories and auto tag any file that gets created or moved inside thad directory.
--Marenz