I was trying to uninstall my Anaconda version of Python and reinstall the regular Python 3.5 version (mac). I used the answer from this SO question to remove the Anaconda folder using
rm -rf ~/anaconda
Pauls-MacBook-Pro:~ paul$ python --version
-bash: /Users/paul/anaconda/bin/python: No such file or directory
Based on your comments, it seems like bash has stored
/Users/paul/anaconda/bin/python as the entry for
python for performance reasons.
hash -d python should remove this entry and use normal path resolution.