What’s so complex about it? From what I gather (after skimming the document just now), you attach an extra element to a message which says how to style which parts of the message, from codepoint n to codepoint m, essentially. At least conceptually, that seems really simple and straightforward.

Are there more elegant or natural ways to do it? Probably. But when you say ‘extremely complex’, saying ‘codepoints 7 to 15 should be bold’ is not what comes to my mind.

You're in XML land. Just do XHTML or whatever subset you think is useful for IM.