This patch doesn't only fix the problem described in bug #1121620 but also resolves the problems with displaying RTL messages on Gaim's IMHtml Widget.
Before my patch MSN conversation used to look like this:

Notice that the direction of the text was automatically (and correctly) detected in the text input field on the bottom. However, the conversation window displays all lines aligned to the left and the text direction is always LTR - therefore RTL text which includes embedded English words (LTR) becomes unreadable because the words are displayed in the wrong order.
The MSN Messenger user will also see the text displayed using the wrong alignment and the wrong direction:



The Code
Writing the patch was a little tricky - some of the code in there may seem like an ugly hack and there's probably a better way of doing some things. But that's the best I could do with my basic knowledge in GTK and Gaim API.
In this patch I implemented the following:
* Added support for [SPAN dir="rtl"] tag in the parser of the IMHtml Widget. (AFAIK this HTML tag is deprecated, but most browsers implement it and it beats coding CSS support)
* Added text direction detection to outgoing messages and send it with the correct SPAN tag.
* Added support for the "RL=1" flag in Messenger protocol implementation, both in sending and receiving messages.
* Fixed some display issues: Insert RLM and RLE Unicode characters to the conversation display according to the expected alignment and direction.
UPDATE:
Now timestamps will show up on the right side:

Hebrew alias + English text
Hebrew alias + Hebrew text
English alias + English text
English alias + Hebrew text