Det beror på vad du väljer för collation när du lagrar datan helt enkelt,
http://dev.mysql.com/doc/mysql/en/charset.html
Det skall fungera att söka direkt, default nuförtiden är dock UTF-8 (iaf på mina servrar), så det är bara att översätta alltihopa till UTF-8 så löser det biffen. Sen så buggar det satan ändå. :)