The issue with "Mrs." is that this title is pretty strongly associated in current American culture with the state of being married.
While it's no longer common, an old-fashioned convention for "Mrs." followed by the title of an office is actually that it refers to the office-holder's wife! E.g. "Mrs. Ambassador" would be the wife of the ambassador (you can actually see this used in the March 2015 Evening Standard article "Mrs Ambassador, you really are spoiling us: why the US ambassador's wife Brooke Barzun is the ultimate hostess with the mostess"). Obviously the U.S. president's wife is usually referred to as the "First Lady" rather than as "Mrs. President," but nonetheless, the title "Mrs. President" still might have the unpleasant connotation that she is married to a "Mr. President", who is the actual office-holder.
At one point, it was possible for "Mrs" to be used as a "courtesy title" that was supposed to denote some level of respect for an older unmarried woman (like a housekeeper), but this is essentially a dead convention, especially with the development of "Ms." as a form of address that is explicitly neutral about marital status.
"Miss" would generally be considered inappropriate as it emphasizes the youth of the person so addressed, so it could be viewed as a way of undermining the president's authority.
The French-derived address "Madam" apparently is generally felt to be a form of address that avoids strongly implying anything about marriage while also sounding more "traditional" (and perhaps more dignified to some people) than "Ms."
"Madam" is already used in the United States as the equivalent of "Mr." when addressing people like cabinet members ("Mr. Secretary" vs. "Madam Secretary"); see Robert Hickey's website for an example.