There is a ProtoBuf.Net fact regarding using AsReference which somehow I missed when digging into why [ProtoAfterDeserialization] attribute is not applied for some objects.
The truth is that it is applied for some but not other objects even if I used AsReference attribute in some places. The AsReference attribute should be applied to ALL REFERENCES TO THE OBJECT, both collections and navigational properties, NOT JUST REFERENCES OTHER THAN THE REFERENCE WE CONSIDER MAIN ONE.

A simple test to prove it is below:

using System.Collections.ObjectModel;
using System.IO;
using System.Linq;
using NUnit.Framework;
using ProtoBuf;

namespace ProtoBufAsReferenceTest
{
    [ProtoContract]
    public class Office
    {
        public static int DeserializationCounter = 0;

        [ProtoMember(1)]
        public Collection<Computer> Computers { get; private set; }

        [ProtoMember(2)]
        public Collection<Person> People { get; private set; }

        public Office()
        {
            Computers = new Collection<Computer>();
            People = new Collection<Person>();
        }

        [ProtoAfterDeserialization]
        protected void OnDeserialize()
        {
            DeserializationCounter++;
            foreach(var computer in Computers)
            {
                computer.Office = this;
            }
            foreach(var person in People)
            {
                person.Office = this;
            }
        }
    }

    [ProtoContract]
    public class Computer
    {
        public static int DeserializationCounter = 0;

        [ProtoMember(1, AsReference = true)]
        public Person Person { get; set; }

        [ProtoIgnore]
        public Office Office { get; set; }

        [ProtoAfterDeserialization]
        protected void OnDeserialize()
        {
            DeserializationCounter++;
        }
    }

    [ProtoContract]
    public class Person
    {
        public static int DeserializationCounter = 0;

        [ProtoMember(1, AsReference = true)]
        public Computer Computer { get; set; }

        [ProtoIgnore]
        public Office Office { get; set; }

        [ProtoAfterDeserialization]
        protected void OnDeserialize()
        {
            DeserializationCounter++;
        }
    }

    [TestFixture]
    public class TestClasses
    {
        [Test]
        public void TestAsReference()
        {
            // 3 instances are created 1 of each type
            var office = new Office();
            var computer = new Computer();
            var developer = new Person();

            office.Computers.Add(computer);
            office.People.Add(developer);
            computer.Person = developer;
            developer.Computer = computer;

            using(var ms = new MemoryStream())
            {
                Serializer.NonGeneric.Serialize(ms, office);
                ms.Position = 0;
                Check(Serializer.Deserialize<Office>(ms));
            }
        }

        private void Check(Office office)
        {
            Assert.AreEqual(1, Office.DeserializationCounter);
            Assert.AreEqual(1, Person.DeserializationCounter); // fails - 2
            Assert.AreEqual(1, Computer.DeserializationCounter); // fails - 2
            var computer = office.People.First().Computer;
            Assert.IsNotNull(computer.Office); // fails - Office is null
        }
    }
}

Office class contains collections of Computers and Peoople without AsReference attribute. Person reference to the Computer for a change uses AsReference attribute. In the end 2 instances of Computer and 2 instances of Person are created.

Only change necessary to fix this problem is adding AsReference to the Office class collections:

        [ProtoMember(1, AsReference = true)]
        public Collection Computers { get; private set; }

        [ProtoMember(2, AsReference = true)]
        public Collection People { get; private set; }

I am not sure if this is common mistake people make when using ProtoBuf.Net but I suspect this might be the case as none of the questions on StackOverflow I've seen in the past mention this.
Or maybe it is only me who when using word "reference" thinks of references to the actual object which implies having at least a single copy of the actual object marked without "AsReference".
Bottom line is if you use AsReference, use it everywhere the object is referenced.