sudo and sudo -i access features

In the first example, the redirection is happening in your current shell and not in the sudo subshell. So sudo is executing echo "search foo.bar.baz" and returning the result to your current shell, which then tries to write it to /etc/resolv.conf.

You could make the first example work by invoking bash directly as your sudo command:

sudo bash -c "echo 'search foo.bar.baz' >> /etc/resolv.conf"

With sudo you can use 1 command with administrator privileges.
With sudo -i you log into the root account, with his own shell and environment variables.
Otherwise you can use sudo -s, with it you log into the root account but you stay with your shell and variables.

Thing is that with sudo -i you may get another shell and another $PATH which can solve the problem.

From the sudo manpage:

-i  The -i (simulate initial login) option runs the shell specified in
    the passwd(5) entry of the user that the command is being run as.
    The command name argument given to the shell begins with a ‘-’ to
    tell the shell to run as a login shell.  sudo attempts to change to
    that user’s home directory before running the shell.  It also ini‐
    tializes the environment, leaving TERM unchanged, setting HOME,
    SHELL, USER, LOGNAME, and PATH, and unsetting all other environment
    variables.  Note that because the shell to use is determined before
    the sudoers file is parsed, a runas_default setting in sudoers will
    specify the user to run the shell as but will not affect which
    shell is actually run.

The problem you're having is that the shell is only applying sudo to the first part of the pipeline you've constructed. The >> etc runs as your permissions rather than root.