My idea is to apply the following changes:

        public void ChangeMessageId(string newId)
        {
            Id = newId;
            CorrelationId = newId;
        }

        [ObsoleteEx(RemoveInVersion = "5.0", TreatAsErrorFromVersion = "4.0", Replacement = "TransportMessage.CorrelationId")]
        public string IdForCorrelation
        {
            get
            {
                return CorrelationId;
            }
        }

        public string CorrelationId
        {
            get
            {
                return correlationId;
            }
            set
            {
                correlationId = value;
                Headers[NServiceBus.Headers.IdForCorrelation] = correlationId;
            }
        }

        string correlationId;

But what should I write then on  the headers constant class?

        [ObsoleteEx(Message = "The IdForCorrelation header is replaced by ???", TreatAsErrorFromVersion = "4.0", RemoveInVersion = "5.0")]
        public const string IdForCorrelation = "CorrId";

And this collides now with the following obsolete definition:

        [ObsoleteEx(Message = "The OriginalId headers is replaced by the IdForCorrelation header since they are now equivalent", RemoveInVersion = "6.0", TreatAsErrorFromVersion = "5.0")]
        public const string OriginalId = "NServiceBus.OriginalId";

How to proceed?