(Please forgive the delay in response. Technical problems prevented the mailing of a number of responses.)

1) Tosfos writes that one should not be surprised that something is forbidden l'Chatchilah by the Torah to do, but that if one did it, this is in order b'Di'eved. Tosfos writes that there are many things, such as holy Kodshim matters, for which "Shinah Alav ha'Kasuv l'Akev"; only when the Torah repeats the prohibition is it invalid even b'Di'eved if one did not fulfill what the Torah said.

2) There may be a source for the above idea from the Gemara in Zevachim (end of 4b), which cites the verse (Devarim 23:24), "You shall guard and do what emanates from your mouth, as you have vowed to Hash-m your G-d; your freewill offering, which you have spoken with your mouth." The Gemara explains that this means that if you did as you vowed, this is considered as a Neder (vow), and if not, it is considered as a Nedavah (freewill offering).

3) Tosfos (beginning of Zevachim 5a) writes that it may be that the source throughout the Talmud for the requirement that the Torah should say something twice for it to be "Me'akev" (to be invalid if one did not do it) is from this verse. Therefore, if one did what one should have done, this is considered as a vow performed in the correct way, but if one did not do it in the correct way, it is still similar to a freewill offering.

4) It may be that this applies not only for Kodshim, but for other areas of the Torah as well the rule of "Shinah Alav ha'Kasuv l'Akev" applies. See the Ran in Pesachim (8b of the pages of the Rif, DH Madichan) who discusses the law of the Gemara in Avodah Zarah (75b) that says that if one buys utensils from a Nochri, he must first Kasher them in boiling water and then immerse them in a Mikveh. However, the Ran cites the Ramban who says that even though one should do it l'Chatchilah in this order, if one did it in the wrong order (i.e., first he immersed them in the Mikveh and only afterwards put the utensils in boiling water), this is also effective. Ramban writes that this law is derived from the verse (Bamidbar 21:23) which tells us that to permit the use of the utensils that were captured from Midyan, "You must pass it through fire and it becomes Tahor." From the words, "pass through fire," we learn that the utensils must first be Kashered through a flame or boiling water. From the words, "becomes Tahor," we learn that they must be immersed in the Mikveh. However, the Ramban writes that if one did this in the opposite order (first he immersed the utensils in the Mikveh, and only afterwards passed them through fire), this is also valid. The reason is that the Torah said only once that one should do it this way, not twice, and therefore the order of events is not Me'akev.

5) In summary, if the Torah states only once that something should be done, we may assume that it is not Me'akev if one does not do it this way. It is only if the Torah went to the extra trouble of writing the Din twice that we say it is invalid even b'Di'eved if performed in the wrong way.

6) However, I have not yet found what the law is if one performs the procedures of Parah Adumah in the wrong order. I hope to deal with this in a future reply.

I did find two sources concerning what are the essential parts of the Parah Adumah service.

a) See the Mishnah in Menachos (27a) which states that the three species used in the Parah Adumah service are all essential. Rashi explains that one must have the cedar branch, the hyssop, and the red string mentioned in Bamidbar 19:6. The Gemara (27a) tells us that the reason why it is invalid if one does not possess all three is that the verse (Bamidbar 19:2) calls the Parah a "Chukah." This is consistent with what Rashi (in our Sugya, Yoma 39b, DH Ki Pligi) cites, that the usage of the word "Chukah" always indicates that if one did not do this, the service is invalidated.

This supports what I wrote above, that if the Torah states something only once, this means that while one certainly is obligated to do it, if one did not do so the service is still valid (if it was not for the fact that the Torah used the word "Chukah").

b) The other source I found is the Kesef Mishneh (Hilchos Parah Adumah 11:1). The Rambam writes that one takes three stalks of hyssop and ties them together as one bundle. The Kesef Mishneh writes that the requirement for a bundle is derived from a Gezeirah Shavah which compares the hyssop of the Parah with the hyssop used when the Bnei Yisrael left Egypt. Just as the Torah states (Bamidbar 19:6) that one takes the hyssop of the Parah, so the Torah states (Shemos 12:22), "And you shall take a hyssop bundle." From the fact that when they left Mitzrayim it had to be a bundle, we learn that the hyssop of the Parah also has to be a bundle.

However, the Kesef Mishneh writes (in his second answer) that despite the fact that we have a Gezeirah Shavah, this was accepted only to teach us that there is a Mitzvah to use a bundle, but if one did not do so it is not Me'akev.

Accordingly, we find also for the Parah Adumah that there is a concept that not everything that is required ideally for the service renders it totally invalid if not performed.

(Perhaps the difference between the Din of the Kesef Mishneh and the aforementined Gemara in Menachos (27a) is that the Gemara in Menachos is referring to items mentioned explicitly in the words of the Torah, while the Kesef Mishneh refers to Dinim which are not stated explicitly but merely derived from a Gezeirah Shavah.)

Kol Tuv,

Dovid Blooom