Did the Israelites have shoes in the wilderness?

Summary: Pretty clearly, they did. What, then, shall we make of Rashi's comment referring to כדרך הולכי יחף שרגליהם נפוחות?

Post: In parashat Ekev:

4. Your clothing did not wear out upon you, nor did your foot swell these forty years.

ד. שִׂמְלָתְךָ לֹא בָלְתָה מֵעָלֶיךָ וְרַגְלְךָ לֹא בָצֵקָה זֶה אַרְבָּעִים שָׁנָה:

Rashi writes:

Your clothing did not wear out: The clouds of glory would rub their [the Israelites’] clothes and clean them so that they looked like freshly laundered clothes. And also their children, as they grew, their clothes grew along with them, like a snail’s shell, which grows along with it- [Pesikta d’Rav Kahana p. 92a]		שמלתך לא בלתה: ענני כבוד היו שפים בכסותם ומגהצים אותם כמין כלים מגוהצים, ואף קטניהם כמו שהיו גדלים היה גדל לבושן עמהם, כלבוש הזה של חומט שגדל עמו:
nor did [your foot] swell: Heb. לֹא בָצֵקָה [This means:] Neither [did your foot] swell like dough בָּצֵק, as [usually happens] with those who walk barefoot, that their feet swell.		לא בצקה: לא נפחה כבצק, כדרך הולכי יחף שרגליהם נפוחות:

One might interpret that second comment as indicating that the Israelites did not wear shoes, and yet there was this special protection from the clouds of glory that their feet did not swell. The problem with such an interpretation is that there is a pasuk, in Devarim 29:4, in parashat Ki Tavo, which clearly indicates that they indeed wore shoes:

4. I led you through the desert for forty years [during which time] your garments did not wear out from upon you, nor did your shoes wear out from upon your feet.

ד. וָאוֹלֵךְ אֶתְכֶם אַרְבָּעִים שָׁנָה בַּמִּדְבָּר לֹא בָלוּ שַׂלְמֹתֵיכֶם מֵעֲלֵיכֶם וְנַעַלְךָ לֹא בָלְתָה מֵעַל רַגְלֶךָ:

If they wore shoes, why should we think that their feet would swell? Based on this particular understanding of Rashi's point, there is an apparent contradiction between Rashi and that distant pasuk, or else between the two pesukim.

The Taz discusses this, mentions that many discuss this problem and propose solutions, but that he doesn't like any of them. Rather, the idea is that the ananei hakavod were rubbing and cleaning the clothing, including the shoes. But if the ananei hakavod represent Hashem's glory, it is not fitting for them to have rubbed the soles of the shoes. And so those soles wore away. Despite this, via Divine favor, their feet did not swell. And so we can establish both pesukim in this manner.

[Now back to my = Josh's = analysis.]

I don't know what the other proposed solutions were -- I could come up with some nice harmonizations myself -- but this strikes me as an extremely unlikely explanation of the pesukim and of Rashi. Partial shoes? Really?

The correct and straightforward solution to this is as Minchas Yehuda (note 3*) gives it. There was never a problem, or contradiction. Rashi isn't saying that the Israelites went about barefoot. Rather, he is explaining this local pasuk in light of that distant pasuk in Devarim 29:4. Because their shoes were kept fresh and didn't wear out -- וְנַעַלְךָ לֹא בָלְתָה מֵעַל רַגְלֶךָ -- they did not have to walk barefoot. And because they did not have to walk barefoot, their feet did not swell --  וְרַגְלְךָ לֹא בָצֵקָה. Because only the feet of barefoot walkers swell -- כדרך הולכי יחף שרגליהם נפוחות -- and these Israelites did not need to walk like those barefoot walkers.

Gur Aryeh says the same straightforward explanation.

If we look in Siftei Chachamim, we see the following two answers: The ones with shoes were those who left Egypt, but those who were born in the midbar did not possess shoes. Mizrachi suggests something rather sensible, that Rashi never said that they barefoot, but just that their feet did not swell in the same manner as those who go barefoot. Thus, the purpose is only to describe the manner of swelling. (And also that they did not come to this manner of swelling because they were not barefoot. This appears to be the same as Gur Aryeh.)

So too does Bartenura explain it.