The problem with the guaranteed version of Data::UUID is that you can't recreate the same UUID a second time. Which means that if you want the same file, you can't just create the Data::UUID to find out what directory it's in - you need to scan them. What is wanted here is a hashing algorithm - put in some piece of data (possibly including characters that cannot be represented on the filesystem), get a directory to store it in, and then be able to retrieve it when you pass in the same piece of data.

I actually have an implementation of this that is ready to go on CPAN ... as soon as my manager allows me to do so.