Example is two balls (whatever's) one at 0 and the other at 100. They both are moving towards each other at a speed of 90 units a measurement and will collide in real life...

Not an expert in multi threading, so not even going to pretend :D But couldn't you solve that issue by simply checking the directions of the moving objects, distance and speed. So if object 1 is moving towards object 2 and they are moving at different speeds, you could measure whether the combined speed of the object would be greater than the distance between them, in that case you know there is a chance of a collision. However you don't know exactly where it would happen, so to solve that you sub divide until the combine speed is less than the distance between them and then make a new check whether that resolve in a collision. If you can keep track of number of cycles each thread have done, some could wait for others etc.

Or maybe it would be possible to even out the cycles. In the example of the bullet only requiring 50 points and able to do 100 cycles per second and the car 500 at only 10 cycles per second, then even it out so they arrive at the same time.

Anyway wild guesses, however i believe you are correct when you say that its not easily solved :D