I can now simulate the movement of just over 1000 ai comprised of 12 polygons each with no loss to fps in a single scene!

Have you tried decoupling AI from the appearance of the model and physics? The AI really doesn't need to know the way the character looks or if it's got its left leg off the ground and only needs simple world state like "how fast am I moving". At distance collisions can be simplified to sphere collisions.

Also if no human players can currently see the AI e.g. it's half way around the other side of the game world then massive shortcuts can be taken in its behaviour e.g. moving from one edge of a game area to another by simply delaying then updating coordinates...