First, let's be clear.
Under the relevant Australian law, this person is an Australian citizen,
This is for two reasons. First, because he or she is descended from someone who was born in Australia in the time period from January 26, 1949 to August 19, 1986 (or who was a British subject born in Australia prior to January 26, 1949), and second, because a child born in Australia after 19 August 1986 (and who is not otherwise an Australian citizen) and who lives in Australia, automatically acquires Australian citizenship on his or her 10th birthday, if the child has not been granted or otherwise acquired Australian citizenship in the meantime. This occurs automatically (by operation of law), and applies irrespective of the immigration status of the child or his/her parents.
So, the question is not one of status as an Australian citizen, but of proof of status as an Australian citizen. This individual is not truly stateless.
Also, even if the parents (contrafactually) were stateless rather than being Australian citizens, which they were, children born in Australia whose parents are stateless and not entitled to any other country's citizenship may in some circumstances apply for and be granted Australian citizenship.
One of the reasons that Australia allows this rule is that in order to deport someone you have to know that the person deported is a citizen of the country to which the person is deported. If you are a stateless person in Australia (as this person is not, but someone might suspect them of being), you can be denied rights the flow from citizenship, rather than merely from being a person or being a resident. But, you can't deport a stateless person because you have no place to deport them to.
Related to this fact is that Australia is a party to the Convention on the Reduction of Statelessness (1961), a multilateral international treaty.
In respect of contracting states:
"Stateless birth" on their territory attracts the grant of their
nationality (article 1).
Otherwise stateless persons may take the nationality of the place of
their birth or of the place where they were found (in the case of a
foundling), otherwise they may take the nationality of one of their
parents (in each case possibly subject to a qualifying period of
residence in that State) (article 2).
A stateless person has some time beyond attaining adulthood to seek to
claim the benefit of the Convention. That time is always at least
three years from the age of eighteen (article 1(5)).
Transfer of territory between states must occur in a manner that
avoids the occurrence of statelessness for persons residing in the
territory transferred.
When a State acquires territory, the inhabitants of that territory
presumptively acquire the nationality of that State (article 10).
Persons otherwise stateless shall be able to take the nationality of
one of their parents (possibly subject to a period of prior residence
not more than three years) (article 4).
Absent circumstances of fraudulent application or disloyalty toward
the contracting state, deprivations and renunciations of citizenship
shall only take effect where a person has or subsequently obtains
another nationality in replacement (article 8).
The United Nations High Commissioner for Refugees (UNHCR) will issue
travel documents evidencing nationality to persons, otherwise
stateless, having a claim of nationality under the convention.
Birth on a sea vessel or aircraft may attract the nationality of the
flag of that vessel or craft (article 3).
Disloyal or certain criminal conduct may limit an individual's ability
to avail the benefit of the Convention (article 8).
The benefit of the Convention may be claimed by guardians on behalf of
children (article 1(1)).
States may impose a period of residence qualification for granting
nationality to persons who may be otherwise stateless. That period is
a maximum five years immediately prior to application and maximum of
ten years overall (article 1(2)).
There is also the question of proof. What suffices as proof sufficient for an immigration and nationality official varies, and there are probably presumptions that would be relevant.
The fact that you are currently resident in Australia, that you have no recollection of living anywhere else or being told that you live anywhere else, your own testimony under oath regarding your place of birth and ancestry, any documentation that exists of you being in Australia in the past, and the fact that you speak English in an Australian accent fluently and speak no other language, would also be evidence of your citizenship or might trigger a presumption in favor of assuming that you are a citizen unless proven otherwise.
The government can also change its processes to fit special circumstances.
For example, during the Vietnam War in which the United States was involved, a significant number of children were born to U.S. soldier fathers and Vietnamese mothers in Vietnam. Ordinarily, under U.S. law, it is necessary to establish that a particular person who is a U.S. citizen was your father. But, in the aftermaths of these births, there was a period of time at least, when anyone born in Vietnam to a Vietnamese mother, who was racially part-Vietnamese and part either European or African in ancestry, was presumed based upon appearance alone to be a child of a U.S. citizen present in Vietnam in connection with the war effort and granted citizenship by birth, with their place of birth and mixed race alone sufficing to establish their citizenship.
It wouldn't be hard to imagine Australia adopting such a rule in the case that you describe.
Also, even if such a per se rule were not adopted, usually the ultimate test in a proceeding to establish citizenship is proof by a preponderance of the evidence that it is more likely than not that this person is an Australian citizen, and that standard could probably be met by any official who was not intentionally inclined to bear ill will to this person or their group. Competent legal representation and expert testimony would likely help the person to establish their citizenship.
