Я решил эту проблему.
Прежде чем я сделаю NSURL * url = [NSURL URLWithString: @ "...."];
Я сначала делаю:
NSString *urlStr = [string stringByAddingPercentEscapesUsingEncoding:NSUTF8StringEncoding];
И когда анализирую этот URL на стороне получателя, я сначала делаю:
NSString *urlString = [[url absoluteString] stringByReplacingPercentEscapesUsingEncoding:NSUTF8StringEncoding]; // url is a NSURL