Hello Erndog:
I am having a retaining wall torn out that is 52 years old and sloping the dirt back on a 45* angle with rip-rap (limestone) to help hold the dirt in place.
Some experience with that wall; it had no footing, no weep holes, no drain pipe and trees lined it all along. I have owned the property for over 15 years now and the wall was cracked and broken up pretty bad the whole time, but it didn't fall over until a kid kicked a couple of sections over. Some of the block cores had reinforcing rods down them and poured full of concrete along with some rods driven into the dirt in an effort to anchor the wall. My back-hoe operator had a dickens of a time ripping it out.
It is good that you have a footer, I would have recommended re-bars sticking up out of the footer into the cores of the blocks, where concrete could be poured in them for reinforcing. An anchor of some sort each 4' would be very helpful too. By all means, get rid of the tree, stump and all.
Glenn