Stemte det. Får riktig resultat om jeg kjører utf8_decode(urlencode($str));

Jeg fatter bare ikke hvor utf8 kom inn i bildet.