It is quite common for a program to need to execute other programs at run time. This can be done in two ways: specifying the full path to the binary or relying on the current path. So which approach is correct? It depends on what you are trying to do.
If the program you need to execute is not a required dependency of your program, using the path to locate it is correct; however, let the user set up a full path in the configuration file, if applicable, so that he can forget about the path. For example, suppose your program can provide extra functionality if the zip command is installed. As it is optional, you can't know its location at configuration time, so it is safe to use the path.
But if the program you have to execute is a required dependency of your program, you should always use a full path to it. How to do it is simple: just add a check in your configure script to locate the binary and use the result to configure your sources. But why you should do this? If the external program is a dependency, your program should always use the same binary - which is detected at configuration time; the only way to ensure this is with full paths. For example, imagine that you have two versions of gettext installed in your system - one that comes with the base OS and one installed from the packages collection. Now suppose that a given program only works with the version in the packages collection; you must ensure that it always runs this version, no matter what the path value is, so that it does not misteriously break for some users.
ATM, I'm "fixing" intltool to use full paths to iconv(1) and all gettext utilities, precisely because these are required dependencies. I'm not sure if the upstream developers will accept this patch, but I'll try ;-) Edit (00:42): the issue is being tracked at bug #152020.