Each metal has a reactivity index. As long as the anode rod is more reactive than the steel, it will be degraded first. If there's enough surface area, in theory anyway, the tank would never rust as long as you maintained enough anode rod volume and surface area. There's lots of info on the web, and it's part of high school chemistry class. http://chemistry.about.com/od/charts...-Of-Metals.htm is one easily found source. Mg and Al are very close to each other, with Mg slightly more reactive, thus potentially a better protector (give similar volume and surface areas of the actual rods). It won't hurt to leave the Al one in there for awhile, then change it. You will likely require an impact wrench to get it out, and it will be harder later, but should come out. An anode won't reverse any existing damage, but it should stop or slow down any from occurring in the future.
Also note, though, that depending on your water chemistry, some anode rods can cause the water to smell, so you may be stuck with one or the other, regardless of how well it might stop internal corrosion.