I think it might depend upon the difference between alternate timelines, and alternate universes, which is kind of a wibbly-wobbly timey-wimey thing in the MU.
The Exiles were all from different timelines of 616, What If's are automatically different timelines of 616, and the Living Tribunal could send Phoenix to another Universe just as it could anything else in creation.
The Cross-Time Caper took Excalibur to different dimensions so there might be more wiggle room for there not being any Phoenix in those dimensions.