Вот правильные кодировки; Первый раз я забыл заменить пробелы на плюсы.
searchString = [searchString stringByReplacingOccurrencesOfString:@" " withString:@"+"];
searchString = [searchString stringByAddingPercentEscapesUsingEncoding:NSUTF8StringEncoding];