Yeah, it's impossible to trace stuff like this. I'm sure that someone, somewhere did it before South Park even existed.
I remember making emoticons very similar to 'xD' back on Prodigy chat rooms.
South Park began August 13th 1997... I wouldn't be surprised if it became popular around the same time, but I'm fairly certain that it would have started before that, yeah.