When cutting down trees to get firewood and logs these things currently spawn at the character's feet while performing the action. Realistically you would first need to cut down the tree and then cut it up into logs and firewood. This should also completely remove the model of the felled tree, apart from a tree stump. Also, trees and bushes should not spawn back on server restart if a structure (base element or tent) has been raised so any part of the tree/bush would clip with the structure. Clearing ground to build where not otherwise possible is an age-old practice that would add more depth and authenticity to DayZ.
A backwards check of built structures versus nearby trees should be manageable at server startup?
Ideally, trees should not grow back on restart at all. I believe trees should be tied to server persistence and only respawn at a full server wipe. That would remove the need for the suggested status check vs structures, and if the felled model is cleared when cut up for wood it should break even on server performance load. It would also make trees a perishable asset over time, which could possibly affect server economy and player behavior in interesting ways.