Can gases be "immiscible"? Anyone know of any examples of gas mixtures that phase separate, analogously to the way immiscible liquids do? 

They would have to be extremely non-ideal. I might guess one might have to be much higher molecular weight than the other and at least one if not both would have to have significant intermolecular interactions (although of different kinds).
Good question but there is no such thing as immiscible gases. Immiscibility is caused by surface energy/tension.  Gases do not have surfaces and therefore lack surface tension.