To get the full path with File::Find, just use $File::Find::name. It's right there in the docs. I am using this on Win32 with no problems.

However, there's nothing really wrong with what you're doing here. Your Locate_Files sub (loss of style points for the init caps) doesn't need to run that regex twice, but that won't save you much. It's not going through the whole file system twice as you feared.