the Devel::NYTProf module directory contains the following file (referenced in the error message in my OP):

/user/perl_modules/lib/perl5/x86_64-linux/Devel/auto/Devel/NYTProf/NYT
+Prof.so
[download]

Which appears to be called using this line in /user/perl_modules/lib/perl5/x86_64-linux/Devel/NYTProf/Core.pm:

XSLoader::load('Devel::NYTProf', $VERSION);
[download]

Based on a cursory search this appears to be a way to include a library of separate C/C++ functions and access them from within perl. Is that correct?

Yes, that's the XS mechanism. (See perlxs for far more information than you want to know now.) The actual C library is loaded by DynaLoader or the simplified XSLoader, and that's where the next part is anwered:

neither perl installation has /user/perl_modules/lib/perl5/x86_64-linux/Devel/auto/Devel/NYTProf/ in its list of ldd paths, so how was /tool/bin/perl able to find NYTProf.so but /usr/bin/perl was not? Also the ldd paths for a given perl installation are completely separate from the paths contained in @INC when that perl executable is run, correct?

In case of Devel::NYTProf, the XS library is searched in @INC, not in the system's library path, because Devel::NYTProf uses XSLoader:

/home/alex>strace -e trace=file -o /tmp/trace perl -MDevel::NYTProf -e
+ 1

/home/alex>grep NYTProf /tmp/trace
execve("/usr/local/bin/perl", ["perl", "-MDevel::NYTProf", "-e", "1"],
+ [/* 39 vars */]) = 0
stat("/usr/local/lib64/perl5/Devel/NYTProf.pmc", 0x7ffce1098b60) = -1 
+ENOENT (No such file or directory)
stat("/usr/local/lib64/perl5/Devel/NYTProf.pm", {st_mode=S_IFREG|0444,
+ st_size=53032, ...}) = 0
open("/usr/local/lib64/perl5/Devel/NYTProf.pm", O_RDONLY) = 4
stat("/usr/local/lib64/perl5/Devel/NYTProf/Core.pmc", 0x7ffce1098b60) 
+= -1 ENOENT (No such file or directory)
stat("/usr/local/lib64/perl5/Devel/NYTProf/Core.pm", {st_mode=S_IFREG|
+0444, st_size=5953, ...}) = 0
open("/usr/local/lib64/perl5/Devel/NYTProf/Core.pm", O_RDONLY) = 4
stat("/usr/local/lib64/perl5/auto/Devel/NYTProf/NYTProf.bs", 0x259d298
+) = -1 ENOENT (No such file or directory)
stat("/usr/local/lib64/perl5/auto/Devel/NYTProf/NYTProf.so", {st_mode=
+S_IFREG|0555, st_size=145632, ...}) = 0
open("/usr/local/lib64/perl5/auto/Devel/NYTProf/NYTProf.so", O_RDONLY|
+O_CLOEXEC) = 4

/home/alex>
[download]

What happens is that perl tries to load Devel::NYTProf from files named Devel/NYTProf.pmc or Devel/NYTProf.pm, in all paths in @INC, stopping at the first found. That's normal behaviour of use/require/do. Devel::NYTProf loads Devel::NYTProf::Core, and perl tries to load it from files named Devel/NYTProf/Core.pmc or Devel/NYTProf/Core.pm.

Then Devel::NYTProf::Core calls XSLoader::load("Devel::NYTProf",...). That's a tiny bit more complicated than shown in XSLoader, where load() is just called as XSLoader::load(__PACKAGE__,...). Usually, Devel::NYTProf would directly call XSLoader, but it seems to have grown so far that it needed to be split in two parts. Not really relevant here.

What happens is that XSLoader::load() more or less just replaces :: by / in the package name, prefixes auto/, and appends the name of the bootstrap and library files. So it tries to find auto/Devel/NYTProf/NYTProf.bs and auto/Devel/NYTProf/NYTProf.so. It tries to search only where the matching *.pm file was found (which makes sense, because that's where the installation tools will place it), but may revert to searching in @INC. See https://metacpan.org/dist/XSLoader/source/XSLoader.pm.

Note that XSLoader actually searches the directory where the calling module was loaded from, not the one for the module name passed as argument. Usually, that's the same file, so it usually makes sense. In case of Devel::NYTProf, it looks a little bit confusing because it uses the directory containing Devel/NYTProf/Core.pm instead of the directory containing Devel/NYTProf.pm to load the XS library for Devel::NYTProf, but again, the installation tools placed all of them below the same directory. So it does not really matter and is right in the common case. You usually don't have two completely different modules A and B, installed below different directories, and have module B load the XS for module A or vice versa.

Alexander