Looby's find is interesting, because he's the first possible sighting of a Joseph Gillies as potential father.
I also noticed that in the household of my great-great-aunt Grace or Grizel Cruickshank, widow of James Stephen, farmer at Coxton, Lhanbryde in 1871, there is a Robert Gillies, farm servant, aged 14, born Rothes.
So curiosity got the better of me and I looked up the 1874 marriage certificate, from which I see that Robert Gillies gave his age as 19 and that he was residing at Coxton, Lhanbryde at the time of his marriage. He gave his father's name as Joseph Gillies, ploughman, deceased, and his mother as Ann Gillies MS Asher, deceased.
So we have Joseph Gillies dying in Rothes in 1858, and Robert Gillies, born Rothes, living in Lhanbryde in 1871 and Robert Gillies marrying in Lhanbryde in 1874.
There's a Joseph Gillies, aged 15, an ag lab at Earnside, Alves, in the 1841 census. His age is a bit out, but could it be 'your' Joseph, I wonder?
Also took a look at the death of Joseph Gillies in 1858. There are some interesting details.
First, he was unmarried. So if he was Robert's father, Robert was illegitimate, which would explain the absence of records in the OPRs, but would suggest that Robert was being less than strictly truthful when he registered his marriage. This is pretty common practice to conceal illegitimacy.
Second, he died at Hillylands of Inchberry, which is the northern extremity of the parish of Rothes, lying on the left bank of the River Spey. See
http://www.geograph.org.uk/gridref/NJ3155Third, his parents were James Gillies, ag lab, and Anne Riddoch, deceased. Not Anne Gillies MS Riddoch. Therefore Joseph was illegitimate, because his parents were not married to one another.
Fourth, he was buried in Dipple kirkard, not Rothes itself, or Dundurcas. Dipple is the closest burial ground to Inchberry.
Fifth, the place of burial was certified by William Gillies 'who had charge of the funeral'. There is just one Williiam Gillies of suitable age in the 1851 and 1861 censuses of Rothes. In 1851 the exact address isn't given, and William is 75, but in 1861 it is Inchberry Hill Farmhouse, and William is a widower, aged 82, born Rothes.
Sixth, the informant was John Gillies, uncle. The household of the above William Gillies includes William's son John, who in 1861 is described as a widower, aged 54. In 1851 he was widowed, aged 40.
William Gillies and Helen Clark had at least two sons, both born in the parish of Rothes: James in 1805 and John in 1808.
James Gillies, aged 55, with wife Elspet and a numerous family, is listed in a house on Hill of Inchberry in 1861, described as pauper and salmon fisher. In 1851 he is described as a labourer with one acre of land.
So pulling that all together I deduce that Joseph Gillies, being the son of James Gillies, was the illegitimate grandson of William Gillies. The family home was at Inchberry. In spite of what Robert says on his marriage certificate, I speculate that Robert himself was also illegitimate, and born in Rothes just before the start of civil registration.
That still leaves open the question why Robert consistently said in later censuses that he was born in Aberdeenshire. Was he trying to distance himself from the Gillies family in Inchberry, and if so, why? Or have I got the complete wrong end of a tempting stick?
I think that if I were you my next step would be to take myself off to the National Records of Scotland in General Register House, Edinburgh, or the Mitchell Library in Glasgow and read through the digitised minutes of the Rothes Kirk Session in the hope that the Session noticed, and took as dim a view of the arrivals of Joseph and Robert as it did of the arrivals of several of my relatives in Rothes in the 19th century.
Then I would go downstairs to the Scotland's People Centre and look up the deaths of every Robert Gillies/Gillis/Gillice etc born within a couple of years on 1854, to see if the son of John G and Ann MacBeath can be eliminated as a possible candidate. If he died somewhere and somewhen else, they you know for certain that he can't be 'your' Robert. Note that not finding his death doesn't prove that he is yours - it could mean that he died outwith Scotland.
I am now beginning vaguely to recall doing some work on this Gillies or Gillis or Gillice family (spellings vary!) many years ago. I will see if I can remember when, why, for whom, and where I put the resulting information.