As a matter of fact at the moment immediately after Mohammed's death Medina has much stronger position as the centre of Islam.
Mecca was relatively "newly conquered" to Islam and the majority of the Muslim armed forces in the conflicts of Mohammed were his followers from Medina. Mecca was important before the rise of Muhammed and after considerable time after his death.
So all in all it is safe to say that caliph of Mecca and caliph of Medina would have similar power and influence in the Arab Muslim world.
But I want to stress the point that Mecca and Medina stood close by for centuries and no city was able to crush the other. Muhammed was exceptionally charismatic leader and even for him it was quite a challenge to unite these cities.
I would point that Mecca only recently knew a political and economical growth in the VII century : you can't really argue of peaceful relations with was one minor city (and even during Muhammad's life (the city wasn't exactly the central point of Hejaz).
While he managed to united the western Arabian tribes under a same leadership, the two Islamic factions, that were less of Meccan or Medinit but refugees from Mecca and Medinits keep to exist depsite the strict equality and merge he proclaimed.
Finally, there's a big difference : nor Mecca or Medina hadn't access to a net of loyalties beyond their own cities before the rise of Islam. After the death of Muhammad, they have to deal with not only unified western Arabian tribes and cities, but with Beduins, eastern Arabia, southern Arabia and the clientele net that existed making them more powerful (and more able to fight each other).
What happened in OTL - that was quite unnatural for the Arabs.
I would be less affirmative : periods of union seems to have existed among Arabs if only regionally. Gindibu's rebellion against Assyria could be an exemple (with the name still existing up to Muhammad's era, maybe indicating a lasting legacy). That the alliances or unions didn't lived on because of tribal structures is another thing, of course.
That is possible if the Romans understand that as long as the Arabs fight the Arabs - the Romans are safe.
But they didn't seem to have understood that during the Ridda Wars, letting their arab clients deal directly with without really being concered about.
What would be different here, as Arabs are less of a threat?