The problem encountered, and the solution to it, is already acknowledged by aitap couple posts above.

When you enter a command, the shell has to successively perform a number of stat calls, each with a $PATH element (a directory) prepended. In order to cut down on those syscalls, a small short-circuiting cache is kept. In perl parlance, this would be $full_path{$name}.

You can check the current state of path cache with the "hash" builtin. To clear the cache, enter "hash -r". To refresh the cache on a particular command, try e.g. "hash perl".