I could split $ENV{PATH} and look in every directory it contains, but that would be a lot of work.

Would it?

use File::Spec::Functions qw( catfile path );
my $foo_available = grep -x catfile( $_, 'foo' ), path;
[download]

(Note grep in scalar context — it returns the number of matches.)

Makeshifts last the longest.