On the other hand, redundancy can be used legitimately for emphasis. The specific case of walking for a long time appears to be one of the more typical uses of the phrase "to walk on foot." It's an admittedly informal corpus search, but in first 40 google hits (some overlapping) that I pulled up using the phrase "walked on foot," there were 12 separate usages where the phrase appeared to emphasize distance walked, and another six clearly contrasted walking with another form of transportation. There also seemed to be a group involving religious contexts.
Uses involving distance emphasis included:
- "He later walked on foot the length and breadth of Norway..."
- "They walked on
foot for five days and nights from Gelati..."
- "...all 238 miles of them were walked on foot..."
Uses involving mode of transport contrast included:
- "...a mounted knight who rode on a horse and a foot soldier who walked on foot."
- "On this occasion Madame Zamenoy walked on foot, thinking that her carriage and horses might be too conspicuous..."
- "He walked on foot, rode on a donkey, or took a boat."
Uses involving religious context included:
- "...his Eminence the head of Islamic Supreme Council of Iraq walked on foot with visitors heading toward holy Karbala"
- "...walked on foot as far as the shrine..."
I think there are parallel cases with other redundant verb phrases that are in common use. The one I can think of offhand is "to call on the phone," but I'm sure there are others. Intuitively, I think our feelings about redundant phrases are on a continuum, with some phrases (e.g. "he ate with his mouth") seeming to require more impetus for the redundancy than others (e.g. "he walked on foot"). Given sufficient justification, such as if a person had previously been tube fed, there could be a reason to use the eating example, but it seems like the explicit contrast is more strongly required in that case.