Helt underbart SimonP! Tack!

Med lite googlande löste sig min problem med strtolower och strlen också. Publicerar min fungerande lösning här under till nästa person som har samma problem.

istället för strtolower():
mb_convert_case($q, MB_CASE_LOWER, "UTF-8");

istället för strlen():
strlen(utf8_decode($q));

Dessa rader ska läggas in efter:
$q = urldecode($q);
if (!isUTF8($q)) $q = utf8_encode($q);

MARKERAR TRÅDEN SOM LÖST.

CarlFredrikHero:
Denna funktion brukar jag köra med istället för strlen