Message message = new Message();
        message.CorrelationId = Guid.NewGuid().ToString();

The above code snippet compiles but when you execute it, you get a System.InvalidOperationException with an ambiguous message:
"Identifier is not in the incorrect format."

There is a typo in the exception above and it should actually say:
"Identifier is not in the CORRECT format."

The InvalidOperationException is thrown because the CorrelationId property cannot be assigned just any string. It takes a string value in a specific format, the same as that of the Id property of System.Messaging.Message. The following code executes successfully.

        Message message1 = new Message();
        Message message2 = new Message();                                    
        message1.CorrelationId = message2.Id;