 In Madlax red shoes are important to the past events that happened  12 years ago. "Red shoes" could be a possible link to Noir, since  Kirika, the young girl, also wear red shoes. In episode 25 you see  that Madlax is also wearing red shoes. Both pairs of red shoes from  both series look exactly alike.