I'm also not a Muslim, so take this answer with a huge grain of salt...
It seems to me that this is not a question of religious legalisms, so much as a question of the political structure of Islam (and how that structure might change following the destruction of Earth). As you know, there are already multiple branches of Islam, with their own distinct religious practices, leaders, and "chains of command." So you shouldn't expect all Muslims to adapt in the same way. (In fact it seems that the four Sunni schools already have somewhat different takes on what to do when the qibla is unknown!)
Any arbitrary rule you can invent, will be invented by some religious leader or other. Pick a set of religious leaders, assign them each a rule, and propagate downward through their flocks (and sideways to their ecumenical peers, if any). Think about what happens at the boundaries: which groups have the political power to override, compromise with, or influence their neighbors' systems?
The pre-existing beliefs of your factions will inform how the rules are initially assigned. I'm not qualified to make up examples (and frankly neither are you! Consult an expert, or at least a couple of Muslims). Some factions will justify their decision based on (arguably shaky application of) hadith; some by analogy with pre-destruction rulings; and so on.
There is a famous passage in Surah Al-Baqarah circa 2:142, relating to that time Muhammad changed the qibla from "toward Jerusalem" to "toward Mecca."
The block-headed will say: “What has turned them away from the direction they formerly observed in Prayer?” Say: “To Allah belong the East and the West; He guides whomsoever He wills onto a Straight Way.”
And it is thus that We appointed you to be the community of the middle way so that you might be witnesses to all mankind and the Messenger might be a witness to you. We appointed the direction which you formerly observed so that We might distinguish those who follow the Messenger from those who turn on their heels. For it was indeed burdensome except for those whom Allah guided. [...]
(three translations, one with commentary)
In that case, the rationale seems to have been "God told me what the new qibla should be, so just do it; if you don't do it then you're not a Muslim anymore." This tactic works only because the Prophet himself did it — it was divine revelation. It doesn't work to justify a post-destruction qibla shift, because revelation isn't happening anymore.
...Or is it? Maybe during or shortly after the destruction of Earth, someone gets a revelation — a Jesus, a Joseph Smith, a Báb — maybe claims to be the Mahdi or maybe claims to be something else entirely. Anyway, someone (or -ones) will certainly get to use the line "God said pray toward the North Pole so just do it or you're not a true Muslim." I don't think that kind of revelation would be compatible with any mainstream branch of Islam, the way it would be compatible with e.g. Mormonism. (See continuous revelation.)
Private religious practice can operate by different rules than public religious practice. It's conceivable to me that at least some households will simply continue praying in the direction of the broom closet, because that was what they did on Earth, and why should they change just because the Earth got destroyed? Familiarity is reassuring.
Side note: All Abrahamic religions are concerned in some degree with the direction of prayer, and would have to come up with some new conventions and symbolisms. For example, maybe Roman Catholic space churches are oriented with the altar toward the sun, in continuity with the old eastern orientation; whereas South-Celestial Baptist space churches are oriented with the exit toward the east, because they want (pick one or more) to imitate the Jewish Temple, to reject the appearance of pagan sun-worship, and/or to stick it to the Catholics.
The huge takeaways here are:
Don't assume all Muslims act the same.
Don't assume that religious behaviors always have legalistic justifications. Usually it's "because this is what my dad did," or "this is what my imam says" — political, interpersonal justifications.
Avoid the uncanny valley. The surest way to piss someone off is to get their religion slightly wrong. Go big or go home.