Nils and Anne no trace

Hi I have run out of ideas trying to trace my gg grandparents, I have plenty of info on them, their parents etc but have lost them both for a 12 year gap. The family has been told that Nils was a royal soldier and Anne was a cook at the royal palace. We have been unable to find any trace for the years 1855 - 67. Nils Anderson born 25/9/1835 Rygge parish, confimed Rygge 25/7/1852 then in 1855 in Moss is god parent to Even Olsen, his brother Oles son. 1867 next shows up in Oslo with the birth of his son Axel 25/9/1867(have hospital records) 16/3/1869 Harald born Gamle Aker Kirkr records, 31/10/1871 Valborg born Gamle Aker records and Gamle Aker Kirke marriage - 84 30/9/1870. Anne Hansdtr born 1/4/1837 in Eidskog confirmed 1855 Vinger parish records then shows up withthe birth of Axel in 1867 in Oslo. We know they lived in Damstredent and Dops Gate in Oslo between 1867 - 72 when they emigrated to New Zealand. The 12 year gap is a struggle to find them, any ideas would be helpful.