I have tidied my PATH by hand before. You may want to check MANPATH too, that can have non-existant or duplicate directories too (depending on your distrib of course).

Update: Also you may want to check that /usr/local/bin is before /usr/bin and /bin, I had a problem with that once (that was because I set them up wrong actually).