Is it in principle possible to store energy more efficiently (per kg) than as antimatter? I'd like to understand if there's a theoretical bound on how efficiently you could, in principle, store energy to be used for propulsion. The important quantity to consider is energy stored per kg of battery, since a heavier battery makes it harder to move. Antimatter seems like an efficient medium for storing energy, so I have that as a baseline.
Is it possible to store energy in any form in a more mass-efficient way than as antimatter? I initially thought you could maybe use something like a really really fast flywheel as a battery... but since there's an equivalence between energy and (relativistic) mass, adding kinetic energy to a flywheel (or any other kinetic battery?) should add mass to the flywheel. It seems like the mass of a battery is always going to be extractable energy (kinetic energy in a flywheel, chemical potential energy in a car battery, antimatter mass in an antimatter battery, etc) plus overhead (whatever mass, heat, and chemical potential energy goes into the physical object storing the extractable energy).
If you keep adding kinetic energy to a kinetic battery, does its energy/mass ratio just approach that of really dense antimatter? Is there some way to store more energy per kilogram of battery, or does the relativistic equivalence between mass and energy put a fundamental limit on how efficiently you can store energy? 
 A: I'm not a physicist, but I will attempt to answer.  Mostly, I will restate a lot of your question and attempt to show why antimatter is the most efficient.
As you know, a 1 kg mix of matter and antimatter can react to create energy of $e=mc^2$ where $m=$ 1 kg.  The principle of mass-energy equivalence says that the energy released also weighs 1 kg.
Now let's apply this to a theoretical flywheel that has a stationary mass of 1 kg.  If we could spin this flywheel fast enough to have an energy equivalent to the 1 kg of matter/antimatter, then the spinning flywheel would weigh 2 kg (1 kg rest mass + 1 kg worth of kinetic energy).  I think this 2 kg is called the relativistic mass.
Now it's easy to see that for any battery to have a better efficiency than matter/antimatter, it would have to have a negative mass before the (1 kg of ) energy is added to it.  In other words, the matter/antimatter "battery" had a mass of zero before the "energy" was added.
Therefore, there can be no battery that exceeds the energy storage of matter/antimatter.
Even if you created flywheels out of matter/antimatter and spun them up, their masses would increase as their spins increase, resulting in the same efficiency as the non-spinning flywheels.
A: Relativistic energy is $E = \sqrt{p^2c^2 + m^2 c^4}$, so while stationary objects with no moving parts have an upper bound of $E=mc^2$ (by, for example, matter-antimatter interaction), the energy of a moving object is only capped by the momentum, $p$. Relativistic momentum, $p$, is $\frac{m v c}{\sqrt{c^2-v^2}}$. This has no upper bound. Once an object travels faster than $\frac{c}{\sqrt{2}}$, it has more kinetic energy than mass-energy. An extremely powerful doughnut shaped track could hold a ring of relativistic particles as they race around, and those particles could have an energy density without theoretical limit. There are, of course, practical considerations that make this as practically unworkable as antimatter.
Contemporary authors mostly avoid the concept of relativistic mass because it is confusing and leads to misconceptions. Clearing those up would require a long, boring discussion of frames and observers. For these purposes, relativistic mass is mathematical bookkeeping which you can ignore.
The Ehrenfest paradox applies to solid, spinning discs. There is no requirement that a spinning object or collection of objects be solid, nor disc-shaped.
There are hundreds of forms of energy storage. Examining all of them to see what the various mass overheads (both for storage and conversion) would take forever. Ask about each individually.
A: 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.
A: As for most questions, a more succinct answer is needed, rather than a more detailed one, so here it is:
Stored energy is equivalent to mass.
Thus we can never store more energy than mass, as the OP already suspected. This is just a very fundamental fact about nature. To understand and accept it, one can study some Special Relativity.
To make some more connections to the original question, note this:


*

*Any battery, flywheel or other device will have an initial, 'empty' mass $M_0$.
Pumping an energy $E$ into the device will make the mass go up to $M = M_0 + E/c^2$. For every practical device, $E/c^2$ is orders of magnitude smaller than $M_0$. 

*For a perfect/idealized device, flywheel or battery, the limit will be $E=Mc^2$, as suspected by OP. Note that $M$ is the total, 'relativistic' mass. The initial mass $M_0$ has no effect on the limit.

*There is nothing special about antimatter. There is an equal amount of energy (i.e. the mass) in every piece of ordinary matter. However, it is quite special that the combination of both potentially sets 'free' all of this energy as photons. Using this in a controlled way is probably quite difficult.

*Every respectable theory will respect Special Relativity, so there are no loopholes to be found in strings, supersymmetry, higher dimensions, etc.

A: Well, first of all, it should be cleared that as velocity increases mass does not increase. So, when an object(in this case the flywheel) gains more kinetic energy, its mass does not increase, rather its inertia increases. that is to say, it becomes harder to accelerate the flywheel as the kinetic energy goes up. So when you add energy to a flywheel of mass 1 kg, the flywheel's mass does not change, but instead it becomes harder to accelerate the flywheel more.
So, let's talk about momentum. Now, usual classical momentum does not hold at high velocities. So, momentum rather than $p = mv$, is instead $p = \gamma mv$, where $\gamma$ is the Lorentz factor. At low speeds $\gamma$ approximates to 1 giving $p = mv$
So, with those facts in mind, this is the answer to your question: Antimatter is the most efficient way to store energy, but there is an more efficient method, to obtain more energy.
Consider two flywheels, one made of matter and another of antimatter, both of mass $\frac{1}{2}$ kg. Now initially let them face each other with a large distance between them. Now using some external force(maybe say magnetic fields), we accelerate them to some arbitrary velocities, say 0.5c and -0.7c respectively(taking the second negative as it moves in opposite direction of first). Now imagine you are moving with the first wheel. I will not include spin to the wheel as it complicates the picture, leading to Ehrenfest's paradox and some general relativity, but, from wheel 1's frame, it is standing still and not moving at all. so the second wheel's velocity(as seen from the first world is $$w = \frac{v_2 - v_1}{1 - \frac{v_1v_2}{c^2}}$$ which turns out to be approximately 0.92c. Now, $$E^2 = m^2c^4 + p^2c^2$$ and $$p = \gamma mw$$ So, due to the momentum factor, you get more energy in the frame of wheel 1 than just $E = mc^2$.
Replying to the first answer by James, you were right in the context that matter/antimatter batteries are the most efficient, but spinning them(or just moving them in a straight line) does not increase it mass, so more efficiency of the battery in terms of energy/kg can be obtained by using a system of two wheels of total mass 1 kg, that move towards each other. More efficiency can't be obtained via different apparatus but instead can be obtained by different methods. I have mentioned one such method. Maybe there are hundreds more that use the same matter/antimatter setup. But generally, the matter/antimatter battery serves best.
Note: Relativistic mass was invented as a simplification to $p = \gamma mv$. Relativistic mass was defined as $m_{rel} = \gamma m_0$ so that the momentum expression turns out to be $p = m_{rel} v$, which is more similar to the classical expression. Even Einstein disapproved of it. When we say "No object travels at light speed because as velocity increases, kinetic energy adds mass and at light speed you get infinite mass", what it should rather mean is "No object travels at light speed because as velocity increases, kinetic energy increases the object's inertia, making it harder to accelerate it to higher speeds."
Regarding a limit to obtain energy: Well, the limit to the energy you can obtain from a stationary object is $E = mc^2$ and for moving objects it is $$E = \sqrt{m^2c^4 + (\gamma mv)^2c^2}$$ As long as nothing is moving at c, the above equation holds. Only massless objects can move at c, therefore massless antimatter has no use in this scenario. You can always use less energy than the limits above, as in the case of nuclear fission, where you only get 1% of the total energy.
A: I think an easy answer to this is that one simply incorporates some other energy storage mechanism into the system in addition to having matter+antimatter.  The resulting system stores more energy than the matter+antimatter system alone.  We could, for example, take our 0.5kg of matter and 0.5kg of antimatter, squish those into black holes, and then separate them by a large distance.  The graviational potential of such a system is pretty easy to calculate.  We could only reasonably use energy until the black holes "collide", which means that they fall within each others' event horizon.  The radius of the event horizon of a 0.5kg black hole is about 7.42e-28m.  The gravitational potential of the system at inifinity (which isn't significantly different from the potential at a millimeter) is about 2.25e+16J.  To compare, $e=mc^2$ for the system gives about 8.99e+16J.  So, the total energy stored in the system is an extra 25% or so.
