Well, with the help of a bit of network sniffing, I've been comparing the message I'm sending to the one a working client is sending. I've started using the encoding UTF-16 and the both messages are identical except for the first 4 bytes at the begining and the last byte at the end of the "working message".
working message begins with: FF FE FF c3 3C
not working message begins with: FE FF 00 3C