I don't like that the FAQ tells you to break the usual order. Rules changes don't belong in the FAQ. It would be better to list the Shelter type before the Victory type if you want the trashing to occur before drawing. Personally, I would prefer simply not having an effect for Shelter or Curse type.
I also disagree with the FAQ mandating an order, but for a different reason.
I know you do cards in order, but wouldn't this be simultaneous events that you choose the order of? I don't think listing one card type before another matters.
No, you do have to do them in order. I believe this is clarified on the Trusty Steed rules. You can't move your deck into your discard pile and THEN draw 2 cards.
*Edit*
Here's a thread about it. Interestingly enough, Pawn rules clarify that you can do either choice in either order (even though with the Pawn choices it never makes any different what order you choose). Donald says he wishes they were consistant, but too late now!
So there's no precedent here. Any card for which it might matter (and on that subject, I looked through all the cards that are similar and there were none (other than Trusty Steed) for which it mattered) would have to specify which method it used.
Pawn, for example, doesn't matter. +1 action, +1 buy, +1$ are all future potential. +1 card is the only do-it-now. Actually, Pawn and Trusty Steed are the only two that I could find that even have a 'choose two'.
All of which is entirely irrelevant anyhow. Iron Maiden is /not/ a 'choose two'. It's a 'If this type...'. I wouldn't automatically apply a ruling from one style of verbiage to another style of verbiage. Key word there is automatically, of course.
I would look at something like Tribute, which deals with multiple cards, to find out if there's a specific order that should be applied. The rules are silent on this point. But again... there's no reason to say anything. The order in which bonuses can be taken cannot possibly matter.