In order to tab-complete "sudo ...", your shell needs a rule that what follows "sudo" is found from $PATH, not cwd. If it has a rule, it can have the rule tab-complete based on /usr/bin and /usr/sbin instead of actually using $PATH (which is likely to include things like ~/bin which won't be in root's PATH, as well as not including /usr/sbin).