I have heard that there is a dispute as to which Bracha you should make on papaya, Ha'Etz or Ha'Adama? Why? (sources)
The question is whether or not it halachically qualifies as a "tree." This has ramifications regarding orlah, as well: In Eretz Yisrael, where even doubtful orlah is forbidden, classifying papaya as a tree fruit would effectively render it prohibited, since most commercially available papaya is from the first three years of the plant's life.
Some views regarding this matter are recorded in a fascinating article by R' Gavriel Price from the OU, excerpted below (but well worth reading in its entirety):
Among the poskim who rule that papaya is a “vegetable”, even in Eretz Yisroel, are Ben Ish Chai (Rav Pa’aim, 2, 30) and Rav Ovadiah Yosef (Ye’chavah Da’as, 4,52).
However, Shevat Halevi (S”T, 6, 165) raises questions on their proofs. Rav Shternbuch also concludes that papaya seems to be, halachically, a tree fruit. If grown in Eretz Yisroel, he rules that one should prohibit papaya as orlah. However, in chutz L’aretz he is lenient, based on the fact that, ultimately, there is an authentic safek as to its status; also, whenever there is a difference of opinion about opinion, we are lenient in chutz l’aretz. Thus, if a person grew a papaya tree in his backyard in Be’er Sheva, the papaya from, say, the first year would be prohibited. But if the tree grew in Brooklyn, the papaya would be permitted. Rav Gedalia Dov Schwartz is also lenient in chutz l’aretz.