I don't exactly see how there can be no guarantees at all. For example, using this greedy method you're at least trivially guaranteed that the number of degree 6 vertices increases. I'm also very surprised that there aren't stronger bounds for some class of well-behaved meshes. I would like to know more, but Google isn't really being helpful :/