I believe that you have to use the ActiveXMessageFormatter, and not the XmlMessageFormatter. The XmlMessageFormatter is for sending objects between .net applications. What you are sending is not xml but string. And not a .net string. According to the documentation of the ActiveXMessageFormatter it is for:
Serializes or deserializes primitive
data types and other objects to or
from the body of a Message Queuing
message, using a format that is
compatible with the MSMQ ActiveX
Component
When you send from vb6 you are using the msmq com interface. Which is another name for ActiveX interface. After you receive the string with the ActiveXMessageFormatter. Convert it to xml object explicitly.