search with non-ASCII characters doesn't work

Search based on non-ASCII characters doesn't work.

The steps:
Add a contact with non-ASCII characters, like Rado?? Mi?dzynarodowa.
Search for the contact with "Rado??"

Current result:
The contact is not found.

Expected result:
The contact is found.

Note: Searching for "Rado" works (i.e., finds the contact).

Note: This is most probably strictly related to CRM-44.