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 What's a good solution for file-tagging in linux?