I had a whole long answer written up saying that it was theoretically possible under federal law, but would almost certainly never happen in reality. However, at the end of my research I found a perfect quote as to why.
This is from a newspaper article during the 2000 recount which culminated in Bush v. Gore, as collected in a 2001 case study about it (emphasis mine):
University of Miami law professor Terence Anderson said
that although Palm Beach County voters might have the
most valid challenge ever under that standard, any kind of
remedy would be difficult to impose. The complaining
voters want the general election results voided and new
voting held for president and vice president in Palm Beach
County.
"I think (those challenging the ballot's validity) can satisfy
the standard, but once they do, the question is, what do we
do now?" Anderson says. "There is no remedy that wouldn't
offend the constitutional values of the rest of the electorate."
If a new vote were ordered, he says, Palm Beach would be in
the unusual position of effectively deciding, on its own, the
nation's next president.
Analysts agree that no Florida court has ever ordered a
new election, and analysts have difficulty finding parallels in
other states.
Either the number of votes found to be problematic isn't enough to change the outcome of the election (even if it causes the state to swing), and thus there's no need for a revote, or it is big enough, in which case the whole country would have to revote in order to ensure it was fair. There have been a few cases where smaller races (such as state-wide ones) have been revoted, as cited in that article, but never a Presidential one.
As it happens, the Western Australia vote you mention in your question is equivalent to those: The entirety of the affected area (i.e. Western Australia) had to revote, not just whatever areas the missing ballots may have come from. But the rest of the country was unaffected, since it was just a state-level position.
