Jonathan Wallace suggested that "God!" functions as a semantic stopsign - that it isn't a propositional assertion, so much as a cognitive traffic signal: do not think past this point. Saying "God!" doesn't so much resolve the paradox, as put up a cognitive traffic signal to halt the obvious continuation of the question-and-answer chain.

I think there's also another, though related explanation. It's that many people evaluate "scientific things" and "religious things" using different criteria.

You could compare this to the difference in the way different literary genres are evaluated. In a conventional detective story, you're not supposed to have anything supernatural. If if turns out that the murderer was actually a ghost or an alien, many readers will find this unsatisfactory and consider themselves cheated. On the other hand, if you're reading a fairy tale, then it's supposed to have unexplainable elements, and would in fact fail to qualify as a fairy tale if it didn't.

The "literary genre of science" is considered something down-to-earth, dealing with ordinary, mundane matters. Sure, it may get complicated, but it's supposed to be logical and not violate common sense. The "literary genre of religion" is supposed to be awe-inspiring and beyond human comprehension.

So if people are told that "Time began with the Big Bang", then that's an incomprehensible explanation in the scientific domain. That's perceived to violate the rules of the scientific domain, and is thus rejected as an explanation. On the other hand, "God has always existed" is an incomprehensible explanation in the religious domain. That's fine, because explanations in the religious domain are supposed to be incomprehensible. So it feels like a satisfying answer.

To anyone who feels that this is obviously idiotic, do note that it kind of makes sense. Even atheists do apply different criteria for evaluating different domains. Explanations that work fine in the domain of chemistry are useless in the domain of sociology, except perhaps as loose metaphors. Compartmentalization is the default action in thought.