This is just for the bash case, but I was under the impression that shells cache and hash the binaries they find in the path to avoid doing these lookups. Surprised by the need for strace showing lookups.
strace bash -c 'ls;ls'
You should not see the lookups for the second ls invocation.