Don't worry too much about the word "matter": the modern view afforded by GTR, quantum field theory and much more means that the word "matter" has become very vague. If you look up the "matter" Wikipedia page, this seems to agree that the word "matter" is very vague now indeed, so as a useful concept in physics, the word seems clearly to have passed its use-by date. I actually got to the age of 45 before one day I realised ashamedly that I couldn't define the word "matter" anymore, a situation I thought was disgraceful for a physicist, but a quick sweep of the web shows that there was good reason for my plight.
Your reasoning is quite correct and you are definitely on the right track. The rest mass of the sealed, reflecting box most definitely increases, by dint of the equation $E^2 = p^2 c^2 + m_0^2 c^4$ you cite. You simply need to think in a bit more detail about what happens when you shove the box: for simplicity, simply assume a one-dimensional cavity with motion only along the cavity's optical axis. The mirror at one end will begin to blue shift the light whose motion is in the opposite direction to the motion and at the other end there will be a red shift back. Whether you analyse this situation classically (messy and hard) or as photons (easy) as done in my answer here, you get the same answer: there is a difference between the impulses imparted to the mirrors at either end by dint of the different light wavelengths, and when you do the calculation it shows that you need to impart an impulse $E \Delta\,v/c^2$ (owing to the presence of the light with energy $E$ alone) to the box to change its speed by $\Delta\,v$. A slightly different method of getting to this conclusion is method 2 in my answer here. Either way, one can see that a great deal of the "rest mass" in the World indeed arises from the confinement of massless objects, as discussed further in my answer here and here.
