The Talmud (Shabbat 24a) questions whether Al HaNissim is appropriate at all within the context of Birkat HaMazon, noting one argument in favor and one against. One the one hand, Channukah and Purim are, as mentioned, rabbinical festivals, while the occasions meriting mention within Ya'aleh V'Yavo are all biblical institutions. However, perhaps the imperative of "pirsumei nisa", publicizing the miracle of the day, warrants inclusion into Birkat HaMazon. The Talmud, still not convinced of any obligation, then considers the proper location for this prayer; R. Sheshet rejects the inclination of R. Huna b. Yehudah to insert it into Boneh Yerushalayim in favor of the current practice of reciting it in the second berakhah ("hoda'ah").
While Al HaNissim has clearly been introduced into the Birkat HaMazon, the question of obligation remains unclear. The Meiri states that while originally recitation was not obligatory (See also She'iltot D'Rav Achai Gaon #26, and Hagahot HaGra to Shulchan Arukh, Orach Chaim 208:12.), current custom has become binding. The codification of the Rambam (Hilkhot Berakhot 2:6), however, implies a mandatory inclusion. The Lechem Mishneh attributes this position to the Talmud Yerushalmi, which not only obligates recitation of Al HaNissim but mandates the repetition of Birkat HaMazon upon its omission. The Rambam thus obligates, at the very least, that Al HaNissim be recited a priori; if it is omitted, however, he would not command repetition of the Birkat HaMazon, in deference to the position of the Talmud Bavli, which demands repetition only when the omitted prayer would have commemorated a festival involving a korban mussaf. As the Bavli does not require repetition, a second recitation would constitue taking G-d's Name in vain. (See also Moadim U’Zmanim, VI, 94, who suggests an alternate understanding of the Rambam’s ruling.)
While current practice is not to repeat Birkat HaMazon when Al HaNissim is omitted (See Rif, Tosafot, Rosh, to Berakhot; Nahar Shalom, Orach Chaim 693:2; Mishnah Berurah 693:15), at least on Channukah, (On Purim, the issue is somewhat more complex; see Shut Terumat HaDeshen #38; Shulchan Arukh, Orach Chaim 695:3; Elyah Rabbah 695:7; Turei Zahav 693:2; Magen Avraham 695:9; Birkei Yosef 695:3; Chayyei Adam 175:32; Mishneh Berurah 695:15 and Sha'ar HaTziyyun #15; Ben Ish Chai, Parshat Tetzaveh #14; Divrei Shirah: Purim #29; Birkat Raphael: Purim #64; and Yemei HaPurim 13:16) there were authorities who disagreed (See the opinion of the Mordechai, quoted by the Beit Yosef, and Ra'avyah). Some decisors (see, for example, Minchat Eliyahu III, 12) suggest that the relevant issue is that of whether or not an obligation exists to have a festive meal on Channukah and Purim. In regards to Ya'aleh V'Yavo, omission warrants repetition when a meal is obligatory; perhaps the same could be said about Al HaNissim. Thus the question would revolve around another debate, that of whether or not such a meal is indeed an obligation on Channukah and Purim.
In interpreting the Talmud’s question about Al HaNissim in Birkat HaMazon, rishonim emphasize additional factors. Rashi notes that specifically prayer, which exists to provide basic praise and thanksgiving, would obviously contain Al HaNissim. Tosafot focus on another factor: prayer takes place in public, and thus serves the aim of pirsumei nisa; Birkat HaMazon, in private, does so to a lesser degree. R. C. A. Turtzin (Kuntres Chanukah U’Megillah, 7) suggests that the difference between Rashi and Tosafot revolves around the question of what is the main reason for the institution of Al HaNissim: is it primarily an expression of thangsgiving, as in Rashi’s focus, or a vehicle for pirsumei nisa, as implied by that of Tosafot.