NSKeyedArchiver doesn't actually encode objects. It simply walks the graph and calls the encode methods of each instances in the graph. Therefore, the most likely source of a leak is inside a custom coder method that you wrote to archive one of your custom classes. You might want to do test archives of individual classes to see if one of them leaks.
The problem with using NSKeyedArchiver to archive a large complex graph is that the entire graph is piled into memory at once. One leak in one classes coder can explode if a lot of instances of that class are archived. If you have 76,000+ objects and just a couple of thousand leak a few bytes each, that will add up in a hurry.
I must add that I have never encountered or even read of a situation in which Core Data did not perform better than an archive for complex graphs regardless of size. Core Data was created specifically to handle just this sort of problem.
If you've tried Core Data and it bogged down, it is probably because you used to much entity inheritance. Since Core Data uses single table inheritance on the store side in SQL, all the descendants of an entity end up in the same table and that bogs things down. Remember, entities are separate from the classes they model so you can have class inheritance without having entity inheritance. That gives you the coding advantages of inheritance without the speed penalty of entity inheritance.