Perhaps you ran ffmpeg on the terminal you removed ffmpeg. That terminal still remembers ffmpeg. If you open a new terminal, it will be gone. You can try this: (i) create /usr/local/bin/aaa which contains
(ii) chmod +x /usr/local/bin/aaa, (iii) run aaa, (iv) rm /usr/local/bin/aaa, (v) run aaa again. See if you get the same error message. There should be a simple command to clear this "cache" but I don't know what it is.