It's got nothing to do with Openfire, but rather the IM Gateway plugin. If you'd like to submit a patch for the IM Gateway plugin to improve upon this though, I'd love to include it!
The thing abot ICQ is... if I recall correctly I -am- sending unicode. Thing is, the target client has to indicate that it supports unicode. (this is the way of ICQ, you have to add a flag to say you support it. if you just up and send unicode to clients, most of them will balk) If there's no unicode flag, we have to send based off the configured encoding. All things considered, ICQ has one of the ugliest language support implementations I've dealt with. =/
