According to Conservation of Momentum, a gun in a sealed box should not have recoil? According to the law of Conservation of Momentum, there is no way to increase the momentum of a system, except by momentum transfer from interactions with the external. If I fire a rifle while sitting on a go kart, the go kart is going to go backwards but the bullet goes forwards, conserving the momentum. 
Now lets say I construct a long 1 inch thick steel box (a few meters long), and I position the gun's butt against the back of it, and fire the gun electronically. Would we not get the box flying backwards still (at least until the bullet gets lodged in the front of the box? Even if the bullet burying in the metal at the end of the box causes another force in the box at the opposite direction of the initial kick, haven't we momentarily broken the conservation of momentum?

 A: To Adress the question you wrote: No, conservation of momentum does hold for all the time, as various other answers showed. The system of box + gun + bullet will at all times have zero momentum. 
However it seems what you really want to know is another question to be answered, namely the question "can there be movement although the momentum is always zero?". 
And as you observed, the answer is "yes". The fact that the sum of all momenta is zero only tells you that the center of mass has to stay at the same spot. The individual parts of the system are however not bound to this law, they can in principle move freely (of course bound to the equations of motion that apply to them), as long as the center of mass stays at it's point. 
You could argue that the system of box, gun and bullet is deformed in the process, with a tiny bit of mass being moved from the right side (the gun) to the left side (the wall of the box). The mass distribution of the box changes due to that process, which leads to a perceived movement if you look just at a PART of the system. 
Adressing the question wether you could in principle have motion without having momentum: This is not possible. We perceive the box moving, while a gun fires a bullet inside, and it will halt when the bullet reaches the other side of the box. However, you can't repeat t his process forever, because each time you do it, metal worth one bullet dissappears at the right side of the box and appears at the left side.  
A: 
haven't we momentarily broken the conservation of momentum?

No.  The box/rifle is only moving backward during the period when the bullet is moving forward.  If you sum their momenta, you will find it sums to zero.
Just because you cannot see the bullet from the outside does not mean that you can ignore its contribution to the momentum of the system.
From comments:

is there not a change in momentum in the opposite direction of the bullet until the moment the bullet strikes the box?

No.  If during the flight of the bullet we examine it, we will find it has some momentum $p$ to the left.  At the same time, the box and rifle will have a momentum $p$ to the right.  In normal cases, the bullet is less massive, so it will have higher speed.  But the magnitude of the momentum is equal.
If you make the bullet heavier and faster, the recoil of the gun/box will just increase to compensate.
A: It seems you completely understand this problem, except between firing and impact, when:
$$ \vec p_{bullet} = -(\vec p_{gun} + \vec p_{box}) $$
so the sum of all three remains $\vec 0$.
A: If the gun is somehow not anchored to the inside of the box when it is fired (say the hook that holds it releases it at the right instant), the gun and bullet will travel in opposite directions with opposite momenta. They may strike the box at different times, but the momentum of gun+box+bullet will always be zero. After both the gun and bullet have hit the sides of the box, and everything has come to rest, the center of mass of gun+box+bullet will be where it was in the beginning.
A: One way of visualizing the difference between the box and the system: (all motion is described relative to the lab frame of reference)
Picture the box, with the loaded rifle clamped as described, and have the box perfectly balanced on a knife-edge.
Temporarily support the box from below (without friction) and fire the rifle, say from right to left.  The box will move to the right briefly before stopping.  The bullet will move briefly to the left until stopping.  The gunpowder, converted to a hot gas, will move from the cartridge, move briefly from right to left, and wind up evenly distributed throughout the box, and averaging out "stopped".
And when the temporary supports under the box are removed, the same, unmoved knife-edge will hold the box in perfect balance again. The knife edge will be in contact with a different part of the box.  But the C of G of the box started above the knife-edge, and ends up above the knife-edge, and the C of G didn't move...
