man tcsh says
rehash Causes the internal hash table of the contents of the directo-
ries in the path variable to be recomputed. This is needed if
new commands are added to directories in path while you are
logged in. This should be necessary only if you add commands
to one of your own directories, or if a systems programmer
changes the contents of one of the system directories. Also
flushes the cache of home directories built by tilde expansion.
In layman's terms: tcsh wants to provide a snappy response, so it builds an internal table (a hash table presumably) of commands and where they are to be found. It presumably does this at start up. Unfortunately it doesn't have any mechanism to notice when you or an administrator do something that would need that table to be updated.
This is one of many reasons why I prefer ksh or bash to csh derivatives.