I am trying to make system calls in php using shell_exec on my
(dedicated) server. Running php 4.3.9 under Redhat EL 4.
It works OK with unix-native commands such as 'ls' or with commands
that I place in the /bin directory. However, if I place a command in
another directory, and call it by full path with shell_exec, nothing
happens. I don't think it is a permission problem, since I can log on
the shell as a different user, and execute the command OK. On the
other hand, I am experiencing this problem only on this particular
server. I have access to two other unix boxes, and none exhibit this
problem, so I am inclined to think there is a configuration problem.
Any ideas ?

I think on this server is open_basedir or safe_mode enabled.

Try to add this line above your shell_exec line:

error_reporting(E_ALL);

It seems most probably a permission problem.  If I were you I would
check the permissions on the bin directory and the files in it.  PHP
will probably run under the uid of the webserver, which, on most
systems is either "apache" or "nobody" depending on the configuration.

It could be a limitation on Apache by SELinux, you can try disabling it to test by:

Opening system-config-securitylevel in X
Disable SELinux protection for Apache, from the SeLinux settings
and restart apache, service httpd restart

SELinux errors also show up in /var/log/messages, you can try a tail
-0f /var/log/messages while running your PHP script to look for
errors.