Если я правильно вас понимаю, вы используете отношения, и они имеют обратную сторону. Если это так, то при удалении одного из них Core Data автоматически удалит другое, и вам не нужно ничего делать.
Что вы видите, что говорит о том, что этого не происходит?
Обновление
Поскольку вы используете несколько потоков, используете ли вы один NSManagedObjectContext
на поток? Если да, обновляете ли вы все потоки при сохранении? Я подозреваю, что один из этих двух не происходит, и поэтому вызывает вашу проблему.