Growing random trees on a lattice $\rightarrow$ Voronoi diagrams
Update:
I think your model for growth has been studied before and goes by the name of the Eden growth model (See section 4 of the (linked) original paper by Murray Eden). It seems what is usually studied is a "site addition" model, whereas your model is a "bond addition" model, but I bet the main results will be the same. I haven't managed to find any recent reviews focusing just on the Eden model yet (and the Wikipedia page is sadly very sparse), but I found a description of it in the first pages of this book chapter of Jean-François Gouyet's "Physics and Fractal Structures".
Famously, the interface of the Eden model was the motivation of Kardar, Parisi and Zhang when they defined the universality class now known as KPZ. Here's a nice review of the KPZ universality class by Ivan Corwin.
Thus a lot is (conjecturally) known about this -- in particular, the size of the fluctuations at the perimeter of a single tree with $N$ bonds should scale as $N^{1/6}$ (fluctuations go as radius$^{1/3}$, and I am pretty sure the radius goes like $N^{1/2}$). Because of this site versus bond addition discrepancy, I haven't found anything about colliding Eden clusters, but I think these ideas can justify that you do get Voronoi cells. I would be delighted to hear criticism or details from an expert!
I don't have anything rigorous to say yet, but some post-facto intuition for Q2 is as follows.
Consider the case of a single seed. I'll tell a story about why the growth from a single seed ought to look more or less like a disk with a wiggly edge, rather than something with a lot of branchy and spread-out fingers (like something one gets out of diffusion-limited aggregation, for instance). If you buy my story, then it should be clearer why there isn't that much "entanglement" at the interfaces between two such growing bodies.
At a given time step $i$, we have a tree $T_i$; let the set of edges that connect $T_i$ to $\mathbb{Z}^2\setminus T_i$ be $G_i$. Then we may form $T_{i+1}$ by choosing uniformly an edge in $G_i$ and adding it to $T_i$. So far, this is just your process in different terms. Here comes some handwaving. Any "protrusions" on $T_i$ will not get too long, because to grow a subset of $T_i$ which sticks out a significant distance from the rest of $T_i$, we'd have to had chosen edges near the "tip" of this protrusion repeatedly. But of course the tip of a long protrusion has a small perimeter compared to the sides of the protrusion, and thus it's much more likely that added edges will smooth out any such features instead of extending them.
Why does this end up with something disk-like? Your process is basically one where you add a "protrusion" to the tree centered somewhere uniformly random on the "boundary". Thus consider the following "off-lattice" version of your process. Let $T_0$ be a disk of radius 1 centered at the origin. $T_i$ is the union of $T_{i-1}$ with a disk centered at a point $p_i$ chosen uniformly from the boundary of $T_{i-1}$. I hope you can see that this is a stochastic version of normal evolution of the boundary. And as is well-known to doodlers, normal evolution tends towards to circular disks, so "intuitively" a stochastic version will tend to a wiggly disk. (One complication here is that your process isn't allowed to form loops in the tree, whereas the continuum version I have in mind does).
Let me just quickly post one additional figure, a nod in the direction suggested by jc and Edmund.
The left image shows the trees for two sites. The right image is a 3D depiction of the same
trees, but this time with each node raised in $z$ by its tree height (with the white dots marking
the two roots, at heights 47 and 55).
(I don't have time at the moment to make a more thorough analysis.)
Continuing to use this "answer" to supplement the comments, here are four random trees grown from one seed, each consisting of about 5000 edges:
And here is zoomed detail from the lower right of the brown tree above:
Q1: It is unlikely that you get the Voronoi diagram. Take a look at "Richardson's growth model" which is closely related (it is your model without the trees). The limit shape there is not a disc, meaning that the model is not rotationally symmetric in the limit, so it's not Voronoi cells.
http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aop/1176994460
- Richard Durrett and Thomas M. Liggett: "The Shape of the Limit Set in Richardson's Growth Model." Ann. Probab. Volume 9, Number 2 (1981), 186-193.