I would second using Tordon on the locust stump. They have a tendancy to send suckers off the root mass if not treated. Instead of one tree you cut down you get many. Locust is also rated fairly highly as firewood (if you can tolerate the thorns). They grow fast and straight, forcing the other trees they are planted with to grow tall quickly (competition for sunlight).
I was told that you can add a couple of strands of baling twine (try the big round bale sissal or plastic) above a normal fence. You can use 2X2's to extend the fence posts up to 7-8 feet. Then run two or three horizontal lines of twine. Let it sag a little so it flutters in the breeze. That way the deer see it. Supposedly they can't judge depth very well (that's way the slanted and offset fences seem to work) and the twine will discourage them from attempting to jump. You might add duct tape stuck on itself here and there to increase visibility. It seemed to help my electric fence when the deer kept running into it.
When I complained about the cost of the plastic tubes, a rep of the company said that you don't need to use it on every tree. I think I was targeting around 800 trees to the acre and he said to do about every third tree. Still, at $1.50-2.00/tube, that's some money. The Army Corp of Engineers uses the tubes with fair success around the Coralville Resevoir. If they work there, they should work anywhere!