Ultimately, for a person of faith, what makes something a miracle isn't if it's rare, or inexplicable, or awe-inspiring, or impossible. It's that you see the hand of God in it, and that's more a question of how you see the world than what you see in the world. If you have a commitment to a purely naturalistic world, you can always hypothesize a naturalistic explanation, even if you don't know what it is. Conversely, if you believe in God, something doesn't have to present as supernatural for you to see God in it.
CS Lewis dramatizes an analogous situation in his Narnia book, The Silver Chair. The heroes, having gotten off-track in their divinely bestowed quest, are astounded to see giant letters carved into the ground saying "UNDER ME." As you might (in your example with the stars), they quite naturally assume a divine explanation. However, in a twist, they learn that there is a naturalistic explanation. The letters are all that remain of a monumental inscription carved into the ground by a vanished civilization. They didn't appear overnight, they were just too large to be recognized as letters when seen from a closer vantage-point.
Lewis' point is this: The letters are both. They are both a meaningless, naturalistically explained, fragment of a relic that is hundreds of years old AND they are a timely, targeted message, forfrom God, for these particular children, at this moment, with regards to this quest. You might well protest, That's just because that's the way that Lewis wrote this. But that also demonstrates his point. If a good author can make a single event serve double duty, why can't a Creator God do the same thing? The message in the stars doesn't necessarily "prove" the existence of God, but even if there was a naturalistic explanation, that wouldn't disprove the existence of God.