Как проверить, что картинка существует?

Ну во-первых, присваивание функции в img.load не даст никакого результата, если хотите повесить обработчик события, то нужно присваивать в img.onload

Во-вторых, данный обработчик работает асинхронно, когда Вы делаете проверку, он еще не выполнился, а выполнится он только тогда, когда картинка загрузится

Ну и наконец в-третьих, если картинки нет, то событие load не произойдет никогда, нужно проверять еще событие error, чтоб отследить ошибку загрузки, а заодно вешать таймаут, дабы не ждать загрузки вечность

Проще всего это реализовать с промисами (если нужна поддержка старых браузеров - то добавьте полифил):

// для начала я вынесу массив с разрешениями из функции, чтоб не создавать его для каждого вызова:
var resolutions = ['maxresdefault', 'hqdefault', 'mqdefault'];
function fetch_highest_res(videoid) {
  // сама функция будет возвращать промис, полученный сверткой массива resolutions
  return resolutions.reduce(
    function(promise, resolution) {
      // перехватываем только ошибку загрузки, если была успешная загрузка - просто отдаем ее дальше
      return promise.catch(function() {
        return new Promise(function(resolve, reject) {
          var img = new Image();
          // повесим таймаут в 3 секунды (если надо, поставьте больше), генерирующий ошибку
          setTimeout(reject, 3000);
          // отследим ошибку загрузки
          img.onerror = reject;
          // а в случае успешной загрузки отдадим результат
          img.onload = function() {
            resolve(resolution);
          };
          // и только когда навесили обработчики начинаем загрузку
          img.src = 'https://i.ytimg.com/vi/' + videoid + '/' + resolution + '.jpg';
        });
      });
    },
    // в качестве инициализирующего значения отдаем отклоненный промис
    // так как следующая картинка должна пробоваться только если не получилось загрузить предыдущую
    // а отслеживать мы это будем по ошибке загрузки
    Promise.reject()
  // ну и перехватим случай, если ничего не удалось загрузить
  ).catch(function() { return null; });
}

// ну и функция теперь у нас возвращает асинхронный результат в виде промиса
// поэтому и получать его надо соответствующе
fetch_highest_res('eei-soH5Gx8').then(function(resolution) {
  console.log(resolution); // hqdefault
});

P.S. сделал все в es5, ибо мало ли, Вам нужна поддержка старья, а сборкой Вы явно не пользуетесь...

function fetch_highest_res(videoid) {
    var resolutions = ["maxresdefault", "sddefault", "hqdefault", "mqdefault"];
    var counter = resolutions.length,
        img_max = new Image;
    return new Promise(function(resolve, reject) {
        resolutions.forEach(function(resolution) {
            var img = new Image;
            img.onerror = function() {
                --counter || resolve(img_max)
            };
            img.onload = function() {
                if (img.width > img_max.width) img_max = img;
                img.onerror()
            };
            img.src = "https://i.ytimg.com/vi/" + videoid + "/" + resolution + ".jpg"
        })
    })
};
fetch_highest_res('eei-soH5Gx8').then(function(img_max) {
  console.log(img_max)
});