Have you had a look at the SQLite documentation for LIKE? It has come information about non ASCII characters and a bug. Maybe Android has an older version of SQLite installed where this is a problem.
I think the second normalised column might be your best option unfortunately.