I've got to put a page together that collrcts all of these things ... a piece on a work-study program in the Tehachapi News makes this claim:

Stankorb was quick to address the long tradition and history of shoe-ing. While many people envision the American old west when they think of blacksmithing traditions, Stankorb explained that Alexander the Great was the first person in history to shoe his horses, thereby expediting his conquering expeditions.

... can't find much on this claim, even on the web.