On Linux you would probably use strace to follow the bouncing ball. So on Solaris you would use truss to do the same thing. Then just write the output to a file and see where one finds it and see if the other is looking in the same place. Adjust as necessary.
I spent another 5 hours on this between running truss and more searching on google... the problem with truss is that I can't run it against the module itself, but I can run it against httpd (apache 1.3) which is loading it. However, the truss output file has no mention of either the auth_ldap.so library or any of the libraries that httpd claims its trying to load. I'm still at a dead-end here, it seems.
Are you following fork/exec calls with truss? Run it with e.g.
truss -fa -t open apachectl start
That will trace the open calls (used by linker) which should show you what you're after.
Also, check pmap -x to see if it's getting loaded by the apache worker threads on the hosts which work.
To search for the files on the server, try e.g.
find / -name 'libldapssl41*'
to search for similarly named files. It might be called something like libldapssl41.so.1 rather than simply .so.