Why even expect binaries to be in the same place on different systems with different default PATHs? Know how many times I've seen problems caused by (#!/usr/bin/bash|#!/bin/bash) pointing to the wrong place?
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!
I've started to dislike /usr/bin/env too. At least use -i. Otherwise you're one PATH manipulation away from executing a malicious program as your intended shell.
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.
No need to make it 100 times harder to read.