I will try to clarify. To simplify the formulae, I will put the speed of light equal to unity, $c=1$, so that if time is seconds, distance is in light seconds and something traveling at half the speed of light has $v=1/2$. Energy-momentum can be written as a 4-vector $(E, \mathbf p)$. The magnitude of energy-momentum is mass, $m$, and obeys the relationship $$m^2=E^2 - |\mathbf p|^2 $$ or $$E^2=m^2 + |\mathbf p|^2 .$$
This is exactly the same equation as used in other answers, but with $c=1$, which makes it look simpler. Mass, $m$, in this relationship is a relativistic invariant quantity, the same in all reference frames. It is also called rest mass. In old treatments, energy, $E$, is sometimes called relativistic mass. That terminology is now generally deprecated, as it causes confusion and there is already a perfectly good word, energy.
Energy-momentum is a conserved quantity. If you add together the energy-momenta for all the particles in a system, then it will always come to the same result so long as nothing leaves or enters the system.
The simplest example I can think of to show the conversion between mass and energy has two identical bodies with equal opposite momenta $( E, \pm \mathbf p )$ flying together and coalescing into a single body. Then energy momentum conservation tells us that the energy-momentum of the final body is given by $$(E, \mathbf p) + (E, -\mathbf p) = (2E, \mathbf 0). $$ Applying the formula above, we can calculate the mass of the final body, $$2E = 2\sqrt{m^2 + |\mathbf p|^2}, $$ which is greater than the combined masses of the original two bodies.
Exactly the same thing happens in all interactions involving energy. Whenever you have a composite body, the total mass of the body consists of the sum of the energy of all of those particles which make up the body. This is the energy of the body in the rest frame.
The same is true of the flywheel, viewed from an inertial frame in which the flywheel is rotating but its centre of mass is not moving (rotating frames are difficult to think about correctly in special relativity). The momenta of all the particles of matter comprising the flywheel sum to zero, meaning there is an increase in mass.
It applies also to any kind of stored energy, such as the energy stored in chemical bonds in an electrical battery.
In other words, it is an absolute law that the energy stored in a battery, of any sort, is equal to the mass reduction when that energy is released.
The only difference with an antimatter battery is that all the mass of the antimatter, together with an exactly equal mass of matter, will be converted to energy. That does place an absolute limit on the amount of energy which can be derived from a given mass, but it does not take into account all the mass of the battery.
For questions of efficiency there are other things to consider. The energy released from a matter-antimatter reaction is difficult to use efficiently (particularly if you were seeking to drive a space-ship).
And if one is thinking of the mass of the battery, at the moment we can only stored tiny amounts of antimatter (a few atoms of anti-hydrogen) for a matter of minutes, and storing it needs extraordinarily sophisticated (and massive) equipment. The problem is that any antimatter touching the storage container will immediately be destroyed, along with the destruction of an equal amount of the container. I honestly doubt whether it would ever be possible to store antimatter for use in a battery.