If this is true, it is sometimes asked, and Tyre and Sidon would have repented, why didn't Jesus go there and do some miracles? Those souls could have been saved, right?

We may respond first by noting that Tyre and Sidon were likely among the first mission fields for the Church, and that there could be little doubt that such signs were done in those cities at some point. But in fact this would have no relevance to this passage. Jesus is not speaking of the Tyre and Sidon of his day, but of those cities hundreds of years before.

The first thing to notice is that Jesus refers to these cities doing the "sackcloth and ashes" repentance -- not turning to him and submitting to his lordship in a salvific sense. Sackcloth and ashes were "common public tokens of repentance" (Blomberg commentary on Matthew, 191), as they were for Nineveh. They indicated a change in behavior and a recognition of judgment.

All that Jesus is saying is that the cities would have done a moral U-turn, like Nineveh did. (And of course, Nineveh eventually reversed that U-turn and fell into wickedness again...we are not talking permanent effects here, nor of any lasting allegiance to the true God.)

Taking it further, Jesus refers here not to the "modern" first century cities, but rather to the cities as they existed in Isaiah's time. His comments about Tyre and Sidon allude to Isaiah 23:1-12. (His comments about Capernaum likewise echo the condemnation of Babylon in Isaiah 14.)

Therefore there is no moral dilemma about God not sending Jesus to Tyre and Sidon for a turnaround. The implications of such a visit are not as eternal as the question supposes, but rather emphasize the greater light and thus greater responsibility of those who witnessed Christ directly.

Critics often object to the reputed unfairness of such judgments upon "babies, the elderly, deaf," etc. in the villages who would not have a chance to hear the message. However, this is merely language of collective representation, which does not at all mean there are not potential exceptions; here Jesus is speaking in the normal mode of the day, on which "all or nothing" language was the norm.