Additionally, it is a common story-telling device of having separate side-plots that intersect with main plot in interesting or surprising ways. These side-plots can be complete stories in their own right (I guess Game of Thrones is the biggest example of this in popular media), or tiny side elements like the creepy old guy from Home Alone.
I’d say OP’s seconds story has an even more minimalist version of this device, which improves the on first story by adding some mystery for the reader (‘What does this description of a meteor have to do with anything?’) and giving this side-story a satisfying conclusion. It also somewhat reduces the bullshit factor of the deus ex machina as explained above.
This comes really close to the ‘This statement is false’-discussion in Gödel-Escher-Bach. On itself, this statement is circular (if it were true, it would become false and vice versa), but when combined with another true/false statement, the full statement is not always circular:
If in “This sentence is false, or I am single”, the “I am single” part is false, then the truth-value of the full statement reduces to that of ‘This sentence is false’ and becomes circular. If ‘I am single’ is true, the whole statement is true independent of the first part, and so the statement is not circular (with ‘this sentence is false’ being true).
I guess the following happens in the Australia example: the Satan-worshipers must always say (full) statements which are false, so they can never set the truth-value of ‘this sentence is false’ to true. This way they are excluded from making “This sentence is false, or …”-type statements.