That's true. It's not deterministic which contact will get processed first. The multi-threading solvers locks the two bodies in a contact during processing.
Multi-threading is off by default. To turn it on you specify a threshold which is the number of active contacts. It's unnecessary to set up threads when you have a small number contacts. You can set thresholds for PositionConstrainsSolver, VelocityConstrainsSolver and Contacts, individually.
It's possible that the contacts does not update the bodies (It doesn't alter position/velocity/etc), but that's something I have to double check, I can't say for sure right now. Although callback events like OnCollision/OnSeperation will fire from different threads. You have to buffer and change object states on the next update.
Farseer has a couple of triangulation tools, maybe you can find an algorithm that reduces the number of fixtures from what you have now.
In most engines you use a simplified approximation for collisions.
You can setup a body with a few fixtures that cover your sprite and subscribe to
Body.OnCollision where you can perform a per-pixel collision. If you return false from
OnCollision() the collision is ignored. For a generic solution you can listen to World.ContactManager.BeginContact and implement a IPixelPerfectCollision interface or something similar on some of your bodies.
Have you tried to add a reference to the body in FixtureProxy?
You could then quickly discard the pair inside .AddPair() without having to get the bodies through fixture, which probably cause a cache-miss.