Drush: Wrong PHP version when trying to sql-sync with SSH
Check the user that is specified in your Drush alias file.  From the error message above, my guess is that you have configured your alias file to use the web server user, and your web server user is probably not configured to use php-cli -- that's probably why you're getting an old php-cgi instead.  Log in as the web server user (you may need to edit /etc/passwd and change the shell to /bin/bash first), and then configure your path and DRUSH_PHP environments as you describe above.

Alternately, you could use some other user in your Drush alias file.  I like to create a user called 'www-admin', or something similar, and make all of my web files owned by that user.