Does the gravestone for Caroline give an exact date of birth? The birth record for Astor says both of his parents were born in 1863, do this does support the birth date you have for Nils.
Most often, not finding someone in the 1865 census doesn't mean they were missed - it is usually a name change problem. For example, you say Nils's mother was possibly "Marie Eriksen". If Marie's father was named Ole Eriksen, Marie might have used "Marie Olsdatter" in 1865, but then changed to "Marie Eriksen" 20 years later. This is just an example of what could be, but I have seen this many times.
Have you taken a closer look at this family?
http://digitalarkivet.arkivverket.no/ft/person/pf01037998003...Brian