Anyone who has seen Noir, will find a lot of similiarities with this show. The main connection being that there are two girls who can't remember their pasts but who are somehow connected. I personally liked Madlax a lot more. One of the reasons is that in Noir, the girls meet right in the first episode. But in Madlax they don't meet until well into the series, but since you always know that they are going to meet eventually, you (or at least I) was constantly wondering when it was going to happen. And that was part of what kept my interest.
Other than that, I think the story in Madlax has two thing going for it: pacing and mood. It achieves this successfully by carefully feeding the audience little pieces of the puzzle each episode, so that each piece adds to the mystery and expands the scope of the story. It's not until near the end that you gradually start to see how everything fits together. By following this pattern, the show keeps the audience wanting to know more and thus makes them want to keep watching because they know that with every episode they are going to learn at least a little more. It's that balance of revelation and mystery that creates the successful blend of pacing and mood.
The characters in the story were great too. You could really feel for them because almost everyone was trying to unravel some potentially unpleasant secret about their past. And with cool names like "Madlax" and "Monday Friday" how could you not love them?
Bee Train (which as I understand it is an offshoot of Production IG) did a great job with this. They also did the animation for Noir and .Hack, but I think this one outshined them all. Again it created just the right mood and was a consistently high quality.
Yuki Kajiura provided an emotionally powerful soundtrack. Her talents are right up there with Yoko Kanno as far as I'm concerned (though I think Kajiura is less versatile than Kanno), and this is her best yet.
The ending of the show was satisfying, climactic, and explained all the key plot elements. What I really liked was that it did not wait to wrap everything up until the last episode. Again this is due to the great pacing of the show. All the key elements were wrapped up over the last 6 or so episodes, thus leaving some breathing room in the last episode to flesh out a proper resolution. There was only thing that I was confused about (it had to do with why a certain character died) , but that may just be my own lack of attention more than a flaw in the story itself.
In summary, I think this is a great series for anyone who really wants some worthwhile entertainment. Just watch it.