Thank you, Ben, for the compliment and also for the questions and comments. Here are some brief replies.
1) This is a subtle and interesting question you raise. The short answer is that the causal structure is unaffected. The reason is that if the world operates in this way, then any local "changes" to the data at one point, corresponding to a causal intervention of some sort, are subject to the constraints as well. In the EPR context, this has led some commentators to claim that violation of Statistical Independence (which is a consequence of the presence of nonlocal constraints) means that we would lack "free will". (See my "Nonlocality without non locality" paper for more discussion and references to related papers by 't Hooft, Conway & Kochen, and others.) My reply in brief is that there is no more of a problem for free will than there already is in our ordinary, fully local theories, in which we typically understand our actions to be constrained or determined by what has occurred in our casusal past.
2) I've been meaning to read Ken's essay - he's done some really interesting work - and I will do so ASAP.
3) Have not seen Dolce's paper, but will print it out and take a look. Thanks for bringing it to my attention!
4) Excellent question. I think that if one has a discrete graph, one has at least a hope of defining locality, though even there it is not clear how to treat neighboring points. My thinking is less radical, hoping that consideration of nonlocal constraints in classical theory will enable us to understand better how to think about quantum theory in general, and quantum gravity in particular.
5) Right - with a metric of some sort defined on a graph, we could have shorter and longer paths. It's not immediately obvious to me why two points with a short path between them might seem to be far apart when viewed at large scales, since this seems similar to the case in ordinary space where two points (Boston and New York, say) are connected by a short path but also by many longer ones (Boston east to Paris to Beijing to LA to New York). In that case, as in this, we'd say they're close together, despite the fact that there are long routes as well. All that said, your point (4) above raises real questions about the general notion of locality once one starts messing around with the spacetime background.
5a) Fractal spaces would seem to exhibit the phenomenon you mention: scale-dependence of distance.