Я бы использовал NSRegularExpression
NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:
@"((?: \\{\\}){3} [0-9]+)" options:0 error:nil];
NSMutableString *str = [NSMutableString stringWithString:
@"{SCENE*169/doprava/doprava_tabulka {} {} {} 1299234095} {SCENE*169/doprava/doprava_video {} {} {} 1299234166}"];
[regex replaceMatchesInString:str options:0 range:NSMakeRange(0, [str length]) withTemplate:@""];
str
значение здесь {SCENE*169/doprava/doprava_tabulka} {SCENE*169/doprava/doprava_video}
Но если вы разрабатываете для iOS, оно доступно только с версии 3.2.