Как пишет один из зарубежных игроков: он сначала прошел весь мировой тур, а потом вернулся на региональный (первый) этап и обновлял команды (кнопка старт в меню карты) пока месси не появился в одном из соревнований.
Видеогайд.

Подсказка выше не точна, Месси появится на региональном этапе только в том случае если в самом начале вы выбрали регион Испания. Есть другой вариант, это для начала пройти World Tour, далее следуем в 4-ый последний этап тура, там есть соревнование в Buenos Aires, постоянно обновляем составы с помощью кнопки START и перед тем как начать проходить выбираем сложность HARD. При таких действиях у меня Месси появился на этой локации дважды, независимо от региона.

Проще всего получить этот трофей на 4 этапе Мирового Тура, выбираете Buenos Aires 2v2 Panna (Buenos Aires Panna!), обновляете команды и ждёте, пока попадётся Барселона, обыгрываете и трофей ваш.

Видеогайд.

После прохождения 4го этапа World Tour в "газетных титрах" сказано, что теперь Месси заявлен в Fifa Street. Скорее всего, именно с этого момента он становится доступен в испытаниях. Лично мне удалось "поймать" его после прохождения World Tour на 4м этапе, испытание Buenos Aires 2v2 Panna. Сложность при поиске не важна - я нашел и обыграл его на Easy.