If you look at all of the opponents he's mauled on the feet, how many of those guys have ever possessed great Muay Thai skills and leg kicks? Vitor Belfort primarily attacks with his hands and very rarely utilises leg kicks. In fact, there isn't a single fighter I can think of who has shown great Muay Thai skills going up against The Spider.
It seems to be that Anderson completely mystifies his opponents with his erratic hand and head movement. His opponents are so concentrated on his hand positioning and how he's moving them back and forth whilst moving his head at the same time, that they forget about the legs and the rest of the body. One great counter to this strategy are leg kicks, hard, fast leg kicks.
And I know this is a huge stretch but if any of you have watched the entire Ryo Chonan fight video, you'll see that Ryo was actually very successful with the leg kicks against Anderson, in fact, he was battering Andersons inside leg for that entire fight. I know that was many moons ago, but it's really the only evidence we have seen of another fighter holding his own and actually doing some damage to Anderson consistently on the feet.
Shogun also possesses great leg kicking ability and could very well counter Anderson's wild head and hand movement with kicks. Food for thought.