There's a "secure path" option in sudoers that you can use to add additional directories to the path that is searched when sudo is invoked.

Most examples will include the standard user path plus /sbin and /usr/sbin but you can add any directories you want to the option.

Isn't that for executing than autocompleting?

Yes, that's correct, it's only about searching the right directories to find and execute the program you asked for.

But autocomplete after sudo doesn't work for me on a stock Debian install anyway, not sure what one needs to do to get around that. I don't really rely on it. If I'm doing enough work that needs root I start the session with "sudo su -" anyway so not having autocomplete after sudo is not a big deal for me.

What if I want to run fsck on a drive image owned by my user? If I can run /sbin/fsck, I can rightly run that on such a file without using sudo.