Although I enjoy using GAIM, it has several issues - most notably a very poor UI experience, which is being worked on in the 2.0 betas (which are perfectly usable, by the way). The second most obvious problem I've been having is to get GAIM to receive Hebrew messages from buddies on ICQ. This issue can be easily fixed by accessing the ICQ account properties and changing the Encoding field:

The default encoding is ISO Western (ISO-8859-1); to get Hebrew properly just disable the account, change the encoding to Windows Hebrew (Windows-1255) and re-enable it. Although not technically correct, ISO Visual Hebrew (ISO-8859-8) seems to work too.

I'm not sure if the Western encoding is indeed the default - I've been importing my account settings since GAIM 1.3 or so - but I'll look into it and file the appropriate bug report (encoding should be set to what is appropriate according to the current locale, at least in Windows).