How To: Many Objects, Pathfinding and Splines

I am creating a game where, at the beginning of a phase, there is a path for many objects to follow. While there are multiple paths possible, using good 'ol A*, the best one is chosen and a spline is created for all objects to use.

During the game, this path can change. This means that when a better path is discovered all new created objects will follow the new path from start to finish. Unfortunately, its the existing objects that have not finished yet that are the problem.

When a change in the path occurs, I have to go through each existing object, determine their own A* path (instead of relying on the main one) and then create separate splines for each of them to follow in order for things to work the way I want it to (shortest path for each object as well as smooth motion).

I have code such that if at any time an object gets back on the main path it will then forego its personal spline and reuse the main one (sometimes this occurs and sometimes it doesn't).

This works up to a point. But as I increase the number of objects, when a change in path occurs, the whole game just stutters until all the objects figure out what they're going to do. I have tried yielding (at random per object) their rediscovery of their own paths but that really doesn't help very much. I guess I could be doing it wrong but this is really not a very complex game, it just has a lot of objects moving around.

There has to be a more efficient way to do this. Should I forego the Main Spline idea and just make every individual object control their own destiny? Even really old games (Total Annihilation) found a way to do this with many different objects.

Anyway, any help would be much appreciated!

Thank you