It is possible to find all the paths to a file with a given inode, in general, using find's -inum option. But this has awful performance for typical filesystems. What options are there to improve performance?
Are there filesystems with special support for this task? Are there updatedb-like utilities that index inodes?
The more general, the better the answer.
Postscript For more on requirements, see http://superuser.com/questions/81563/whats-a-good-solution-for-file-tagging-in-linux/97245#97245