That means that the row or table collation (not the database collation) is actually not case and accent insensitive, so it differs from the database collation.
There are tweaks to force utf8_ci collation to the selected rows on php level, but it’s not the best solution as it ignores database table indexing.
You should check the row collations on the post_title and the post_content rows as well as the table collation.
The search uses “LIKE” commands to find content, and the LIKE command respects the database collation on SQL level.
If you try a select command on your database via phpMyAdmin like:
SELECT post_title as title FROM wp_posts WHERE post_title LIKE '%search phrase%'
where you replace the “search phrase” with the accented characters, you will get no results either.
However a query like this might return results:
SELECT CONVERT(post_title USING utf8) as title FROM wp_posts WHERE post_title LIKE BINARY _utf8'%search phrase%'
If so, then I might be able to suggest a solution, but I highly recommend checking the collations for rows and tables first.