Why doesn't sudo -E actually preserve my environment?

You can set the exempt_group option to tell sudo to keep the PATH for users in that group.

For example, say your user is in the group 'sys'. Add the following to your sudoers file

Defaults exempt_group="sys"

Now your user will not have PATH reset for sudo commands (-E is not needed for this to work).
See the man page for more details.

EDIT: Going to have to note this as a bad answer. It is true that it works, but it has a side effect I didnt notice while playing with it. It also exempts users in that group from having to type their password. Seems you cant get PATH preservation without allowing this. Bit stupid I think...

Proposing another solution in addition to the one I already entered. This works for bash only (but can be modified for other shells).

The following is a wrapper around sudo that will look for the command youre passing to it. Once it finds the command it changes it to the fully qualified path.
So in effect sudo echo hello becomes sudo /bin/echo hello.

Put the following in your ~/.bashrc

function sudo() {
   local ARGS
   declare -a ARGS=()
   while (( $# )); do
      if [[ "${1:0:1}" == "-" ]]; then
         # the argument is a dash-arg; '-s' for example
         ARGS[${#ARGS[@]}]="$1"
         if [[ "$1" =~ ^-[pugD]$ ]]; then
            # these are the arguments that take a parameter, so skip the next
            ARGS[${#ARGS[@]}]="$2"
            shift
         fi
         shift
      elif [[ "$1" == *"="* ]]; then
         # the argument is a env var to set, not a command
         ARGS[${#ARGS[@]}]="$1"
         shift
      else
         # finally, a command
         CMD="$(which --skip-alias --skip-functions "$1")"
         [[ -z "$CMD" ]] && ARGS[${#ARGS[@]}]="$1" || ARGS[${#ARGS[@]}]="$CMD"
         shift
         break
      fi
   done
   command sudo "${ARGS[@]}" "$@"
}

Note, it wont properly handle it if you have a command with an = in its name. This is extremely unlikely, so I accepted this caveat to keep it simple.