Linux binary can't find shared library, but works while running in strace

Linux binary can't find shared library, but works while running in strace

(Note: names of the binary and binary and library below are obfuscated to
protect the innocent. ;-) The app is proprietary under NDA but the
behavior may not depend on it.)
I have a Linux binary which prints the following error when run:
binary: error while loading shared libraries: libshared.so: cannot open
shared object file: No such file or directory
Which is confusing on its own since libshared.so is in the
LD_LIBRARY_PATH. However,
The library is found correctly when running ldd binary (i.e., the ldd
output points to the file location)
The library is found correctly when running strace binary, so that the
program manages to print its usage information!
I have never seen an application which behaves differently when run on its
own vs in strace, but I figure maybe someone else has seen this happen
before? Any ideas how to resolve this?
I don't have the source so I can't rebuild. Running the app in production
under strace is probably a non-starter. The OS is RHEL 6.2.