Let us return to the chiddush of the Brisker Rov: He maintains that if the requirement of וגונב מבית האיש is not met [such as stealing from a גנב or stealing an אבידה] then there is an exclusion from the entire דין of  גניבה. He further proved this from the Rambam who writes [Gneiva 3-13] that if one steals from a גוי or from hekdesh, he is not sold in order to pay the principal etc. We see that one who steals from a גוי or from hekdesh is obligated in the קרן even though he is not sold. We have to understand why this is so!! The commentaries did not provide a source for this. Explained the Rov that according to his chiddush we can understand very well. The exclusion of הקדש and עכו"ם from the din of גניבה from the word רעהו [see Bava Kamma 62b] means that the entire act of stealing from the aforementioned sources can't be defined as גניבה. Hence, it was pashut to the Rambam that there is no דין of ונמכר בגניבתו and the קרן that must be paid is because of the גזילה, because with respect to גזילה it doesn't say רעהו.  

 נשוב עתה לדברי הגרי"ז, דהוא פליג וסבר דוגונב מבית האיש הוא מיעוט מכל דין גניבה. הנה אמר לי הגרי"ז דכן מוכח ברמב"ם, דכתב (פ"ג מגניבה הי"ג) גנב את העכו"ם או הקדש אינו נמכר על הקרן וכו'. ומבואר דגונב עכו"ם והקדש חייב בקרן ואעפ"כ לית ביה דינא דונמכר בגניבתו. וצ"ב טעם הדבר, והנו"כ לא כתבו מקור לדין זה, ואמר הגרי"ז דלפי דבריו ניחא, דהמיעוט דממעטינן מרעהו עכו"ם והקדש (או מוגונב מבית האיש ולא מבית הקדש), זהו ג"כ מיעוט מכל הדין גניבה, ולהכי היה פשוט להרמב"ם דאין בהם דין דונמכר בגניבתו, והקרן דחייב לשלם הוא מחיובי גזילה, דבגזילה לא כתיב רעהו וכמש"נ.

However, there is a serious problem with the assumption of the Brisker Rov that stealing from a גוי or הקדש is under the rubric of דיני גזילה. The gemara in Shavuos [37b] excludes קרקע from all  חיובי גזילה from the pasuk וכחש בעמיתו - he denied his friend. The Toras Kohanim [כ"ב] excludes a גוי and הקדש from the very same words. That would mean that there are no חויבי גזילה for a גוי or הקדש!!? So how can the Rov say that if one steals from a גוי he is חייב קרן because of the דין גזילה? But then again, this is also a question on the Rambam himself who said that if one steals from a גוי or הקדש he is חייב קרן and likely that includes that he is חייב for גזילה. What about the exclusion in the Toras Kohanim? So we have to say that the pasuk וכחש בעמיתו is referring to payment of the extra fifth and the חיוב קרבן when the receiving of a פקדון is falsely denied but not the payment of the קרן. This is what the Rambam writes [גזילה ואבידה ז-ז] that if someone falsely swears to a גוי he pays the קרן but not the extra fifth as it says וכחש בעמיתו. 

But we have to understand why when it comes to קרקע is the exclusion from גזילה complete whereas when it comes to a גוי and הקדש it is only partial??  

We have to say that Chazal understood that when it comes to קרקע, since it can't be stolen [try putting someone's property in the back of your minivan and sneaking away....], the exclusion from דיני גזילה is complete. Whereas when it comes to stealing from a גוי or הקדש where stealing is a realistic possibility, the exclusion is only from קרבן and the fifth but not from the חיוב קרן.   

אלא דיש לי מקום עיון במה שהעלה הגרי"ז דחיוב קרן דגונב מעכו"ם והקדש הוא מדין גזילה, דהא בקרא כתיב (ויקרא ה, כא) וכחש בעמיתו בפקדון או בתשומת יד או בגזל וגו' ובהמשך שם (כה) והשיב את הגזילה אשר גזל וגו'. ובשבועות (ל"ז ב) ממעטי מהך קרא דוכחש בעמיתו קרקעות עבדים ושטרות, ע"ש בהפלוגתא דר"א ורבנן אי קרקע נגזלת, ואליבא דר"א דקרקע נגזלת וחייב עכ"פ קרן נחלקו שם אי מודה ר"א להמיעוטא דעבדים שטרות וקרקעות לגבי חומש וקרבן, ומ"מ רבנן דרשי מהך קרא דליכא כלל דין גזילה בדברים אלו, דמה הפרט מפורש דבר המטלטל וגופו ממון וכו' יצאו קרקעות עבדים ושטרות ע"ש. הנה לרבנן ילפינן מהאי קרא דקרקע אינה נגזלת ונתמעט קרקע מכל דיני גזילה, והשתא קשה דהא ברישא דהאי קרא כתיב "וכחש בעמיתו" דמיניה ילפינן פרט לשל עכו"ם ושל אחרים, א"כ נמצא דעכו"ם והקדש נמי נתמעטו מעיקר חיוב גזילה, וקשה על דברי הגרי"ז דעכו"ם חייב בקרן מדין גזילה. אולם באמת יקשה כן על דברי הרמב"ם עצמו דהגונב מן העכו"ם וההקדש חייב קרן, ומסתמא ה"ה בגזילה, וכן חזינן דעת התוס' (פסחים כ"ט. ד"ה בדין) דבגזל מנכרי ה"ה חייב באחריותו. ועכצ"ל לדעתם דהקרא דוכחש בעמיתו קאי רק אחומש וקרבן דכפירת הפקדון, וכלשון הרמב"ם (פ"ז מגזו"א ה"ז) "הנשבע לעכו"ם משלם את הקרן ואינו חייב בחומש שנאמר וכחש בעמיתו", ואולם צ"ע מאי שנא דהמיעוט לענין קרקע ממעט מדין גזילה לגמרי, ואילו המיעוט דעכו"ם הוא רק לענין חומש וקרבן.

וצ"ל דהכי קים להו לחז"ל לדרוש, משום דגם גבי קרקע המיעוט מחומש וקרבן אינו גזה"כ בלא טעם אלא סברא הוא דקרקע אינה נגזלת, וכן בעבדים, (ואם היה שייך לגזול קרקע אפשר דהיה חייב חומש), ולכן המיעוט הוא מכל דיני גזילה. משא"כ גבי עכו"ם דאינו מיעוט מעיקר דין גזילה, דהא לא שייך לומר דחפצי הגוי אינם נגזלים כמו בקרקע, אלא הפטור הוא מן החיובים, ע"כ איכא למימר דנתמעט רק מחיובי חומש וקרבן, אבל חיובי גזילה דקרן חייב.