My recommendation is to replace your 500+ fetches with a single fetch. First extract all downloaded IDs in a single array using KVC.
NSArray *downloadedIDs = [downloadedRecords valueForKeyPath:@"identifier"];
Then do a single fetch with this predicate:
[NSPredicate predicateWithFormat:@"identifier in %@", downloadedIDs];
Now you can iterate through the remaining IDs to create new objects. To get the remaining IDS is also very simple once you extract the existing IDs as above:
NSArray *existingIDs = [fetchedObjects valueForKeyPath:@"identifier"];
NSArray *remainingIDs = [downloadedIDs filteredArrayUsingPredicate:
[NSPredicate predicateWithFormat:@"self not in %@", existingIDs]];
There are some possible further optimisations, e.g. by just fetching the identifier properties, but in my experience the above should solve your performance problems.