I've managed to answer a few of the latter questions. <b>Theorem.</b> There is an uncountable graph Γ that is not a Cayley graph in the set-theoretic universe V, but which is a Cayley graph in a larger set-theoretic universe, obtained by forcing. Proof. Let Γ be a directed graph that is a tree, such that all vertices have infinite in-out degree, but such that some of these degrees are countable and some uncountable. For example, perhaps all the in-degrees are countable and all out-degrees are uncountable. It is not difficult to construct such a graph. Clearly, Γ cannot be a Cayley graph, since the degrees don't match. Denote the (current) set-theoretic universe by V, and perform forcing to a forcing extension V[G] in which Γ is countable. (It is a remarkable fact about forcing that any set at all can become countable in a forcing extension.) In the extension V[G], the graph Γ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, Γ is the Cayley graph of the free group on countably many generators.QED <b>Theorem.</b> There is a graph Γ, which is not a Cayley graph, but every finite subgraph of Γ is part of a Cayley graph. Indeed, every finite subgraph of Γ can be extended to an infinite subgraph of Γ that is a Cayley graph. Proof. The same graph Γ as above works. Every finite subgraph of Γ involves only finitely many edges, and can be placed into an infinite subgraph of Γ that is the Cayley graph of the free group on countably many generators. QED The conclusion is that you cannot tell if an uncountable graph is a Cayley graph by looking only at the finite subgraphs. These observations show that in the uncountable case, one should just restrict the question at the outset to graphs satisfying the degree-matching condition.