You can have `/usr/local/bin` in the root's `$PATH` but just doing `sudo` does not give you root's profile where that `PATH` is set
you will get it after logging on as root with
su -
or
sudo -i
Those give you a root shell.
If you want to stay on one line, try using
sudo su -c 'my_prog'
if that doesnt work enforce it with -l
sudo su -l -c 'my_prog'