Excellent question! Your question may be divided into two separate points :

(a) How can the Gemara say that when the word "Na'ara" (without a "Heh") appears in the verse, it implies even a Ketanah? We find this word used in the verse regarding the punishment of Misah for a Na'arah ha'Me'urasah, in the section dealing with Motzi Shem Ra, which certainly is referring only to a Gedolah!

In fact, besides the two verses which you mentioned from the section dealing with Motzi Shem Ra, we find in the section dealing with a Na'arah Me'urasah who allowed herself to be seduced (Pituy) that the Torah refers to her as a "Na'ara" (without a "Heh") when teaching that she is to be killed (see Devarim 22:24). Your question, then, applies there as well.

(b) Even if we reconcile the wording in the verses mentioned above, how is it possible to learn from the word "Na'arah" (with a "Heh"), written with regard to the Kenas of Motzi Shem Ra, that in every place that it is written without a "Heh" that it refers even to a Ketanah? This cannot be the reason why it is written with a "Heh" in the Pasuk referring to Motzi Shem Ra (i.e. to imply only a Gedolah), because if so, then it should write "Na'arah" (with a "Heh") throughout all of the verses of Motzi Shem Ra! It must be that the word is spelled with a "Heh" to teach some other Halachah, which applies only to the Kenas of Motzi Shem Ra (where "Na'arah" is written with a "Heh") and not to the other laws of Na'arah, such as her stoning when she is found guilty (where "Na'ara" is written without a "Heh").

Let us address these two questions, one by one:

(a) The fact that the Torah uses the word "Na'ara" (without a Heh) even when it refers to the punishments which only a Gedolah receives, does not contradict the Gemara's assertion. The Gemara's intention is not that "Na'ara" implies only a Ketanah, nor does the word "Na'ara" imply that the law written in the verse applies also to a Ketanah. Rather, the Gemara's intention is that "Na'ara" is a general term that can include any young woman until the age of Bogeres. Accordingly, wherever there is no necessity to limit the Halachah being taught by the verse to a Na'arah (age twelve), then the term "Na'ara" denotes both a Na'arah and a Ketanah. Conversely, wherever we find that the Torah excludes a Ketanah from the Halachah discussed in the verse, then the word "Na'ara" is to be interpreted to be referring only to a Na'arah of twelve years of age. Therefore, wherever the Torah writes the word "Na'ara" without a "Heh" with regard to a Chiyuv Misah (which applies only to a Gedolah), it must be referring only a Na'arah of twelve years of age. This does not conflict with the principle of the Gemara here that "Na'ara" implies a girl from one day old to a Bogeres.

Even so, this does not begin to answer your second question.

2. The simplest answer would be that the Torah writes the word "Na'arah" with the extra "Heh" only in one place in order to teach us that without a "Heh," the word "Na'ara" includes a Ketanah as well. Once the Torah has taught us this, it no longer saw it necessary to add the extra "Heh" in other places (even where the word "Na'ara" refers only to a Gedolah). This approach, though, is somewhat forced.

Rather, it seems that the answer is as follows. TOSFOS (40b, DH Ha) points out that from the words of the Chachamim in Sanhedrin (66b), it is clear that even the verse that describes the stoning of the Na'arah ha'Me'urasah is talking about both a Na'arah and a Ketanah . Even though we obviously do not administer Misah to a Ketanah, nevertheless the other things Halachos associated with the Na'ara's stoning which are mentioned in the verse do apply to a Ketanah ha'Me'urasah (such as stoning the man who had relations with her). If so, how can the Gemara prove from the fact that the Na'arah mentioned in the section of Motzi Shem Ra gets Misah if she was Mezanah, that the other verses in that Parshah (the verses dealing with payment of Kenas if she was not Mezanah) are referring also just to a Na'arah (and not a Ketanah)? Why does the Gemara say that we do not need a Pasuk to teach that the Kenas of Motzi Shem Ra is limited to a Na'arah? (See Tosfos there who suggests two answers, and the Shitah Mekubetzes there in the name of Tosfos who suggests a third answer, and Tosfos on 44b DH Ha Lav Hachi, who suggests a fourth answer.)

What we see from Tosfos -- no matter which of the answers to his question we accept -- is that the Chiyuv of Sekilah for one who has relations with a Na'arah ha'Me'urasah applies also to one who has relations with a Ketanah (according to the Chachamim who argue with Rebbi Meir in Sanhedrin 66b, as we noted above). If so, the verse discussing the stoning of the Na'arah ha'Me'urasah and her seducer, and the verse discussing the stoning of the wife in a case of Motzi Shem Ra, is not really limited to a Na'arah, but applies to a Ketanah as well. (We might add, to further clarify this point, that in truth, even a Ketanah should be stoned for her purposeful transgression; it is just that the Torah had mercy on her because of her age, as the Gemara says in Sanhedrin 55b.)

According to this, it is clear why the Chiyuv of Sekilah of the Na'arah ha'Me'urasah cannot be written with a "Heh." The verses discussing the stoning are also applicable to a Ketanah, who is fit to receive Sekilah (but is exempted from another reason -- she is underage). This has practical ramifications with regard to the adulterer, who is a Gadol and will receive Sekilah (and not Chenek) for having relations with the Ketanah Me'urasah. Only in the verse that discusses the Kenas of Motzi Shem Ra (when the girl was not Mezanah) does the Torah write "Na'arah" with a "Heh" to teach that one is completely exempt from the Kenas from being Motzi Shem Ra about a Ketanah, as our Sugya says (since Hotza'as Shem Ra on a Ketanah is not as serious a disgrace to the father, see Tosfos 40b ibid.).

However, all that we have said above answers the question only according to the Chachamim who argue with Rebbi Meir, for they say that a man who commits adultery with a Ketanah Me'urasah is punished with Sekilah. However, according to Rebbi Meir (Sanhedrin ibid.), one who commits adultery with a Ketanah is exempt from the Chiyuv of Sekilah (just as the Ketanah is) and only receives Chenek. If so, your question remains; the Torah should have written Na'arah with a "Heh" even when it discusses the stoning of a Na'arah ha'Me'urasah.

The answer is that Tosfos (44b, DH Ha Kol) already pointed out that Rebbi Meir does not agree with the entire rule that "Na'ara" without a "Heh" refers even to a Ketanah. "Na'arah" with a Heh and "Na'ara" without are similar in meaning; they refer only to a Na'arah and not a Ketanah.

According to Rebbi Meir, then, why indeed does the Torah write "Na'arah" with a "Heh" in the verse of Kenas of Motzi Shem Ra?

It must be, like the CHIZKUNI and other Rishonim write, that the other Na'aros of this Parshah (such as Anusah and Mefutah and a Na'arah ha'Me'urasah who is stoned) are written without a "Heh" because they are "lacking"; they sinned or were violated. The only "Na'arah" thatis spelled in a complete and whole manner, i.e. with a "Heh," is the one discussing the Kenas of Motzi Shem Ra, since in that verse the girl did not sin at all, and she is indeed "whole" and clean of any blemish -- which is why her husband must pay a penalty to her father.

However, the Chizkuni's approach is difficult to understand, since we find in Parshas Chayei Sarah that the word "Na'ara" is written without a "Heh" even when it refers to Rivka. Rivka, at the time Eliezer first met her, was certainly free of any blemish and complete and pure in the fullest sense. Why, then, is the word "Na'ara" written there without a "Heh?"

It could be that indeed we find that immediately after she accepted the Kidushin, Eliezer stopped calling her "Na'ara" (without a "Heh"). This is to show that once she had found her intended Chasan, now she was considered complete in the fullest sense! Only her mother and brothers, in the verses in which they try to push off the Shiduch, continued to call her "Na'ara" without a "Heh," as if to say that they wanted her to remain without the Shiduch and lacking. Na'arah with a Heh, then, may indeed imply a "complete" and full Na'arah.

M. Kornfeld