When he married in Perth, Western Australia on 1908, he gave his age as 36 and his parents as Richard Stewart and Margaret Cromer.
On his daughter's birth certificate, his own birthplace is stated to be Tipperlinn Lodge, Morningside, Edinburgh.
I searched all the records for Richard Stewarts born in the Edinburgh area between 1870 and 1874, but none answered to this description.
Neither did any Richard Stewart aged between 7 and 11 on the 1881 census.
No marriages of Richard Stewart to Margaret Cromer occurred either.
I tried searching for a few more years and a wider area, but still nothing.
(If my client had been using pay-per-view to do this, it would have cost far more than my fee).
His war records were in the name of Richard Stewart, which was the name he had used since joining the army, before going out to Australia.
So what next ?
I looked up Tipperlinn Lodge in the 1871 census.
It was the gatekeeper's lodge just outside the walls of the Royal Edinburgh Hospital, then called the Royal Edinburgh Asylum.
(It was probably the small building currently occupied by the Nurses's Union).
The inhabitants of the West Lodge in 1871 were a family called Stewart.
Richard and Betsy Stewart were a middle-aged couple from Perth, whose children (if any) had left home. They were married in 1848, but did not have their children's births registered.
The inhabitants of the East Lodge were a family called Crombie (with 6 children, but none named Margaret), but unfortunately these turned out not to be related. An older daughter who had married the son of the family next door would have fitted perfectly, but it was not to be. There was no Richard Stewart - Margaret Crombie marriage either.
When you hit a brick wall, try the IGI for inspiration.
Playing around with the search engine and trying different combinations of names, I eventually found Richard Stewart Cromer, born 1871 in Edinburgh, son of George Cromer and Margaret m/s Stewart
A quick look at his birth certificate revealed that this was clearly the right person, born 17 Aug 1871 at Tipperlinn Lodge, Edinburgh, son of George Cromer and Margaret m/s Stewart married 11 Aug 1870 Edinburgh.
The marriage certificate revealed that she was the daughter of Richard & Betsy Stewart, and had been living at Tipperlinn Lodge at the time of her marriage.
Clearly she went back to her mother to have her first child, as was usual at that time.
The subsequent history of the family is a mystery. Neither George nor Margaret have death certificates. In the 1881 census, Richard (aged 9) was boarding with another family. His grandparents had moved from the lodge.
It seems that he joined the Kings Own Scottish Borderers as Richard Stewart, dropping his last name. Then, when he married some years later and had to give the names of his parents, he had to switch their surnames to match.