I have been playing with this same basic deck for over a year now and have kept adding to it as new sets came out. I played this as the only deck that took me from gold to master this season. It has a good matchup against a lot of control and armory and attrition decks, it can be a bit soft to agro but the matchup is not a lost cause if you keep a grenadin heavy hand and hit a few removal spells. Other token agro decks are probably the worst matchup which contain queen or other praxis token agro. As their decks are more all in on killing fast with rally obelisk or queen. Disjunction, Banish and Bore are the bane of this decks existence. Torrent of spiders is an all star in the deck and is the main win condition in terms of shutting down the enemy fatties and eventually using them to attack for lethal or force them to trade.
This deck is surprisingly good against all flier decks now with the addition of sandstorm scarf. It can often be marketed for and then held for turn 5 or 6 when hopefully the enemy has expended their market options and are setting up for their icaria. Even if you get bore'd you will often have drawn enough cards from vault of the praxis to make it so you still have a chance. If they don't have bore or any relic destruction the win rate becomes 90+%.
Plan A with the deck is to get a vault of the praxis into play and ride the value train to victory. Most control and midrange players mistake it for an agro deck which it really isnt, and rarely wins before turn 7. You can race sometimes if you dont fear sweepers and you get an obelisk, but that is plan B or C. This deck is great at sitting around and dropping a double creature every turn drawing cards and building up to 8 power where one or multiple obelisks will shut the door. With the merchant the main thing to fetch first is vault of the praxis if you feel you will have time to draw cards. Turn 3 merchant leading to turn 4 having 5 power and playing a vault of the praxis + grenadin drone is what I am trying to do all the time if possible. Initiate of the sands can also help get you going faster and is another creature to pair with merchant to draw cards off vault in a turn.
The influence might be a little rough because you're split pretty much evenly between the three factions. However you only need double time and that's only by turn 4 so it might not be a problem at all. But you should try to reduce one of the factions so you aren't split so evenly between them. Also I think the Xenan Crest is better than the Stonescar one since you're primarily time. Maybe run 4 Xenan Crest and 0-2 Stonescar Crests.
I think you're probably right about Madness not being great in your deck. In my experience Madness needs either a aggressive deck or 2 playsets of sac outlets to really work and you don't have either. So Madness probably won't work unless you find room for 4 Devour.
I think Devour is better than Quarry since it draws two cards and Quarry has two influences. If you end up running 4 Devour then Madness will become much more viable so that might be worth experimenting with over Vara's Choice. But you're right that Vara's Choice does kind of the same thing and it fits better in your current deck so that might just be better.
The removal package seems fine, only having one Annihilate seems a little suspect but like you said, Scout and Markets make it a lot more viable. I'm not sure about only 3 Torch, but that might be right in a deck like this. Purify is bad in this deck, you already have access silence, and both damange and non-damage based removal so there's no reason to run it. I do really think you should try to find room in your market for Striking Snake Formation though, I think you'd get into a lot of board stalls with this deck and Formation just breaks those wide open. You can get through board stalls by outvaluing them with Vault and Obelisk, but that gives them a lot of time to break it themselves. I don't know what you'd cut for it though.
Overall this deck seems pretty solid, you did a good job building it. The main things I'd look at changing is settling on Quarry or Devour (probably Devour) and either getting rid of Madness or trying 3-4x Devour and 2x Madness. You could keep Madness as a one-of but I feel like it's better to decide whether you want it or not for consistencies sake.
Other than that Temple Scribe seems like a card you really want to be running, it'll make the influence a little harder but you already need double time so it won't be that big a deal. I'm not sure what to cut but Initiate of the Sands seems a little out of place. I'd have to play the deck to be sure though, I could see Initiate being really good in this type of shell.