I created 2 discussions, because I believed that there were 2 problems. But the cause of 2 was the same - the Search table in database.
Here are 2 discussions:
http://punbb.org/forums/viewtopic.php?id=16365 (mine)
and
http://punbb.org/forums/viewtopic.php?id=9146
I found the solution in coolhd's post (about chineese caracters) - the WORD line in search_words table has to be changed from Varchar to Varbinary.
For me - it works!