As for collisions, they will only be detected after the fact and the previous position should be restored, but this should not matter much. I am somewhat confident that other special cases could be resolved as well (e.g. two inserters inserting into the same chest with only one slot left, etc.) through a small amount of clever code (e.g. inserters reserving a slot before inserting). Some of these tricks would reduce performance slightly, but the net gain should still be positive.
This would preserve determinism 100%. As I don't have access to the codebase, I can't show off a prototopye implementation though

EDIT: My inserter example would, in fact, not preserve determinism. hmm... I suppose you could implement a priority system based on the id/memory address of the involved objects. The higher/lower number wins the race, and the other must restore previous state.
Please note that I am not saying this should be implemented, I just can't help trying to come up with solutions to problems
