Originally Posted by MTK358
I actually wanted to suggest that the hash table was the problem, but I wouldn't imagine that it would not automatically remove the hash entry and search again if a command is not found.
And me neither, that would be (was) bizarre behaviour.
Could the symptoms be explained by an errant command_not_found_handle() function? Or, more likely, a shopt -u checkhash