It's just how bash works. If there's an entry in the session cache, it uses it. Since executable paths only get cached when you run a command successfully, this only happens when it gets moved from one directory in your PATH to another after you run it once, which isn't that common.

Setting PATH or calling hash -r will clear the session cache or one could run set +h which will disable it altogether.