How does a photon able to store an arbitrary amount of energy? "Regular" particles "accommodate" the energy they carry in their mass and velocity, and their frequency (or wavelength) is tied to those properties (e.g. de Broglie wavelength).
The energy of a photon, on the other hand, appears to be arbitrary, i.e. not tied to mass (which is zero) nor speed (which is the speed of light). Is there an intuitive way to understand how that magical particle is able to store an arbitrary amount of energy?
 A: Photons , as quantum mechanical entities, have a wavefunction . This is a solution of a quantized form of Maxwell's equations, thus the continuity between the quantum level of photons that just have energy and spin when measured, to the classical electromagnetic wave is secured by the same differential equation solutions, in the two different frameworks, classical and quantized.

the E and B in the equation are the electric and magnetic fields entering the classical  too.
For the wavefunction when complex conjugate squared one gets the probability of finding the photon at a delta(volume ) at time delta(t). 
For the classical electromagnetic wave the E field is connected to 

the rate of energy transport S is perpendicular to both E and B and in the direction of propagation of the wave. A condition of the wave solution for a plane wave is Bm = Em/c so that the average intensity for a plane wave can be written


To get the photon energy one has to operate with the energy operator on the wave function of the photon and will get a probability density of the energy, which will be the h*nu within a certain volume, according to the link above.
Thus the energy of the photon is as arbitrary as any other energy concept, and it is carried by energy=h*nu where nu is the frequency of the emergent classical wave by mathematical continuity of the Maxwell equations in both regimes.
I think that the main reason the photon wave function is not discussed is because the classical wave of Maxwell's equations is so successful that it is not necessary to delve into the intricate connection at the level of solving equations. In Quantum Field Theory it can be shown how the classical fields emerge from the underlying quantum mechanical, a demonstration here.
This link discussing the connection between the classical polarized EM wave and the photons that build it up might help the intuition.
A: It's stored in the electromagnetic fields, and it is intrinsically tied to the frequency of the photon.
Also, consider that "regular particles" also accommodate energy in many different forms besides mass/velocity.  Consider nuclear power as an example, which is stored in a way that does not show up trivially in mass or velocity (technically it shows up in mass, but in a way which is far less intuitive than the energy of photons)
