As I mentioned in my response to this post, the bounds on chemically-powered magic are limited by the energy density of the chemicals that power it. I think it's acceptable in your story to assume that life will evolve (probably at the microscopic level) to eat any high-energy compound you provide. If your magicians are decent geneticists and sufficiently unethical, they might even inject those genes into their own offspring. At this point, you have your power source.
According to the Wikipedia article on Energy Density, sugar provides 16 MJ/kg of usable energy. Coal, by comparison, provides about 30 MJ/kg, and Methane is
at the high end of the energy scale, providing 55MJ/kg. Fats, butane, and most automotive fuels fall in the middle of this scale. Note that the most energetic compounds are actually gaseous, so a high density per unit volume is hard to achieve.
My favorite standard of chemical energy, the Big Mac sandwich, provides 2MJ of energy.
If your "magic" (or SF) is based on electrical manipulation, these energy levels can get you surprisingly far. One kilowatt-hour of electricity is 3.6MJ, or less than two Big Macs. If you want to zap someone like an electric eel, that's a big pulse.
Unfortunately, the kind of things you may often want to do with magic require correspondingly massive amounts of energy. The current RDA for an adult male is ~10.5MJ (5 Big Macs). Think of how much work that same human can do in a day; that gives you some idea of the order of magnitude of work that your magic can do with that same amount of energy.
At the same time, it's significant that explosives like TNT or gunpowder actually have a much lower energy density than the items I mentioned above. They work not because of the amount of energy they provide, but the speed at which that energy is delivered. If you can convert those same 5 Big Macs into a single explosion, that's equivalent to 11 sticks of dynamite.
Now, since we're working with magic, it's also possible that this same energy is being used to open a transdimensional portal somewhere. In that case, we're no longer limited by the amount of energy provided by this superfood, but how much energy is available through the portal. You are no longer limited by chemical energy densities, and the sky's the limit.
Having slept on this, I realize that the ideal solution to the chemical question was staring me in the face all along: metallic aluminum. Aluminum is a reasonably common metal, and at 31 MJ/kg, has a moderately high energy density. You can transport it as a relatively stable solid, but with the right (presumably organic) catalyst, your hypothetical mages could extract that energy as needed.
In nature, one wouldn't expect to find anything that eats aluminum, because you don't find free aluminum in nature -- it's all tied up as an oxide, in bauxite ore. But mankind has changed that, and in a million years, perhaps nature would have responded to that change in environment.
The fun part, of course, happens when your mages want to consume aluminum. As you've already noted, being able to snort aluminum powder, while bad for the lungs, would give a quickly-absorbed energy burst. But if that same powder is left lying out in the open, a breeze might pick it up, and suddenly you have a fuel-air explosive.