Thanks, your response is much appreciated.
I used Advanced Outlook Repair...as I said - did not work, it created more mess... :-(
I upgraded the Outlook 2003 to 2007 on another machine, but still unable to type Hebrew (or any right-left language for that matter). Is it possible that the reason is that this is an upgrade and not a clean install?
Regarding the encoding - I'll have to check tomorrow in the office.
[Send to myself] - no, I cannot type Hebrew at all in Outlook, it seems like the existence of IMAP account disables it. However if you send me a message with Hebrew in the subject line, to both IMAP and POP accounts, the one in POP will show up correctly and the one in IMAP will display questions marks in the subject line. Again - this is only the subject line, the Hebrew in message body clear and readable.