The Maharal notes that Haman’s advisers must have known that Mordechai was a Jew, as Haman, himself mentioned to them (Esther 5:13). After all, it was possible that Mordechai was brought into Persia with King Yechanya (Esther 2:6), but was not actually a Jew. Therefore, the Talmud (Megillah 16a) understands the advisers’ remarks as relating to Mordechai’s tribal lineage. In effect, they were saying that if he were from the tribe of Yehudah, Binyamin, Efrayim, or Menasheh, Haman could not expect to be successful against him. In Bireishis (49:8), Yaakov promised Yehudah that his descendants would conquer their enemies. In Tehillim (80:3), King David prays that H-Shem strengthen Efrayim, Binyamin, and Menasheh. As it happens, Mordechai could trace his paternal lineage to one of these listed tribes and his maternal lineage to another.
The Maharal points out that Yehudah, Efrayim and Binyamin all represent Jewish unity because the Beis HaMikdash, and the Mishkan in Shilo and Nov were all located in their tribal inheritance. As proof, the Maharal quotes from the verse (Bamidbar 16:6) in which Moshe attempts to quell the rebellion of Korach and his group by saying they should all bring fire-pans. The entire group bringing individual fire-pans would represent the very opposite of unity. In fact, the unity of Jews’ uniqueness with H-Shem’s Uniqueness fights off the doubts and confusion that Amalek represents. The Midrash (Esther Rabbah 6:2) considers the description “Yehudi” as being derived from the adjective “yechidi” (“unique”) or the noun echad, (“one”).
According to the Targum, the advisers were not asking if Mordechai was a Jew, but if he were from the holier, saintly Jews. The Vilna Gaon writes that, unlike Haman’s assertion that the events he described were chance, Zeresh and the advisers were saying that it was not. After all, as a member of the Yehudim, Mordechai enjoyed the situation promised by the Talmud (Shabbos 156a, Nedarim 32a) that “ein mazal b’Yisroel” (“there is not mazal for Israel”).
R’ Dovid Feinstein explains that the advisers were focusing on the fact that Haman’s situation could go either way, based on Jews’ behavior.
The Ginzei HaMelech quotes R’ Meir Shapiro, who focused on the word, “zerah” (“seed”). They were saying that if the Jewish youth had no serious connection to Mordechai. They considered the aged Mordechai only powerful if he still held relevant sway on the youth of his people. So when Haman told them that Mordechai was surrounded by thousands of students learning a (temporarily) outmoded law regarding grains and Temple service, the advisers realized Haman has no chance. When Judaism is relevant for the invigorated youth, our enemies stand no chance.
Similarly, says the Ginzei HaMelech, Mordechai has to be mizerah (“from the seed”) of Yehudim – an invigorated member of the youth in vitality – and then Haman should just give up.
According to the Ben Ish Chai, Haman gave a short history lesson saying Mordechai was a descendant of Shaul, who only ruled briefly and not successfully. In response, the advisers said, that may be true, but Mordechai was also a descendant of Yehudah from his mother’s side, so he will win as promised. Homiletically, he reads the word im (if) as eim (mother).