Emoji is a Japanese word, which is the biggest hint they didn't come from Microsoft. (And yes, its a specific subset of Unicode characters, though that proper use is getting diluted by people using it to refer to any and every inline pictograph in text, even non-Unicode ones, a use more similar to "emoticon" from the 90s… that word seems to have faded into obscurity, largely supplanted by "emoji")
Even "emoticons"¹, or pictographs replacing some text like ":-)" (which is how they were called before the west imported "emoji", largely because it showed up in phone IMEs after its inclusion in Unicode) were definitely a thing in the late 90s. I suspect AIM must have had them before Messenger, but frankly, I didn't think anyone actually used Messenger except maybe business types?
Everyone I seemed to know was on AIM, with a few odd exceptions on Yahoo, if they were normal. If they were more nerdy, IRC, but that was text based. (Though some clients would still translate certain text sequences into pictures. I'm pretty sure, e.g., Trillian could/would, but I don't remember when I adopted it. But it could have been earlier than 2003.)
¹The picture version. As I recall the usage of this word in the late 90s/early '00s, it could mean either ":-)" as text, or the pictogram version thereof, largely because clients at the time would just convert between the two freely. One end might send text, but the receiving client would pictogram it.