I modified the question (increasing the depth of the trees results in more predictions that disagree) and added some visualizations. I'll also ask on GitHub when I can.

Thanks for the answer. It might be worth digging into the sklearn code to find out what is non-deterministic. I'm still working on looking at the trees, but it seems like if bootstrap=False and all the features are used, then each tree in the forest is exactly the same!

I asked the question here. Still working on visualizing the individual trees, but it appears setting bootstrap=False and using all the features does not produce identical random forests, at least in Scikit-Learn. Whether this is because of the particular implementation remains to be seen!

This seems like an interesting question to test. Should be pretty doable with Sklearn since you can even print out the individual trees to see if they are the same.

This is a great explanation! Does this mean if bootstrap=False and each split uses all the features (no random subsampling) then the forest is not random?