Which is the right sequence of play ?
1 ) Example
(Play before you declare any invasions - force an opponent to discard a maester card at random )
I pay Melisandre 200 gold and I tell that Baratheon's player discard a master card. He have only one master card that he will play "at any time" ... can Baratheon play on answer to Melisandre ?
I think yes because is "at any time"
This is by no means official, but I think no, because you declared you were using Melisandre before your opponent could declare he was using his Maester card. (The only exception I could imagine, and I am not sure if such a card exists, would be a Maester card that allows you to cancel a character ability that was just used against you.) It seems unfair to allow the target of Melisandre to use the Maester card before losing it.
By the way, how could you target the Baratheon player with Melisandre anyway?
Edit: I don't know about your second question. What I am unsure about is whether Tyrell could still declare he is using Margaery AFTER Lannister has declared he is using Tywin. I think it would be a poor choice for Tyrell to do so, though. Lannister only has to re-roll one die, so he will still have one 6 (5+1) to match the Tyrell's 6 and odds are good (2/3) that the re-rolled second defense die will still beat Tyrell's 4, his second highest die.