Aha! I've been looking for an illustration of these traditional horse shoes for a long time. I read about them in an old travel guide describing Japan (I have lost the reference). It described how on long mountain roads there were men every few miles selling woven horse shoes. The shoes were more like the rubber boots some horses wear today. They were woven of reeds, and tied over the hoof. They cushioned the hoof from rocks, but wore out very quickly. However, they were relatively cheap, so one could stop every few miles and buy a new pair if needed.
Here is a wonderful old photo from Okinawa Soba's photostream. It is a digital image from a very old slide, dating back to around 1890. Visit the flickr page to read more about the image, and to see a few more old images of horses in Japan, each with a nice long description and explanation.