Cron, for example, doesn't have the same $PATH as your login shell. So no full paths means you can fail to run some commands, or run the wrong copy of one.
There's also the security aspect. If your script has "." in it's $PATH, or something else writeable, I may be able to coerce it to run an imposter command.
No need to make it 100 times harder to read.
After reading this thread though, I'm not sure I want to suggest people write `#!/usr/bin/env bash` either... since that depends on the path being correctly set, and bash being in the path!
Situations exist where you need more granularity.
There's also things like "watch" and "at" you might use in a shell script. They don't inherit the parent's environment, so setting PATH doesn't help.
You're correct in that "full paths" isn't a definitive answer though. I suppose the more generic advice to not depend on your environment to have it right is better.