How can I randomly generate bounded height spanning trees?
I was working on bounded-depth spanning trees a few years ago, they're really interesting.  Some of my colleagues came up with message passing algorithms that did a great job, but I can't find any of their code available.  We wrote it up in a physics style here:  http://iopscience.iop.org/1742-5468/2009/12/P12010/.  They've told me that it also works with degree bounds, although that didn't make it into the paper.

The approach you propose, which I would call Markov Chain Monte Carlo, is often a competitor to the message passing approach.  If you are interested in sampling approximately uniformly at random from the set of bounded-degree, bounded-depth spanning trees of a given graph, I suggest altering your approach to use "soft" bounds.  I.e. instead of rejecting an edge swap that makes the tree violate the depth bound, accept it, but with lower probability than a swap which does not violate the bound.  If you have a parameter that controls how much lower this probability is, you can make the constraint violating configurations less and less probable until you arrive at a feasible solution that is nearly uniformly random.

The big question is how long do you need to run the chain.  Since a spanning tree with degree at most 2 is a Hamiltonian path, you should expect any generic bound to be exponential in the size of the graph.  But maybe the graphs you are interested in are special in some way.