Hi Denis,
I am really sorry for the delay of this reply as it weekends for all of us here.
It seems like for some reason when joomla trying to redirect the search query in SEF format, it will somehow convert the unicode value with a different value. Refer my example below.
// The correct value
Utilização
// Query changed by joomla redirection
Utilização
I believe that this behavior is somehow related with your older version of Joomla (2.5.16) as the search query is working fine with joomla 2.5.28 (latest version of joomla 2.5.x). Can you try to update your joomla to latest version of 2.5.28 or joomla 3 and see how it goes?
In the meantime, we are still investigating on the issue and we will inform you once we have find some lead about the issue here. Thanks for the understanding.