If it hits the ice shouldn't the bullet be deformed? The vids looks like the bullet was spun like a top.
I agree about the deformation part, which I can't figure out. Maybe ice has some special little-known property under high impact velocities that makes it act like a sheet of rubber or something, then the bullet just sits there using up its considerable rotational energy.
As I said, this phenomenon has been reported for a long time, but was usually dismissed as being tall tales by mountain men, who are generally a little bit dotty anyhow. After all, who would voluntarily trudge around the mountains all winter in "ten feet of snow and twenty below" except someone who was a bit "off" in the head?

But with the advent of the internet and portable video cameras, it has been sufficiently documented, to my mind, to qualify as a real phenomenon worthy of real physicists' attention.
After all, one of the parameters of scientific investigation is that the experiment has to be repeatable by independent observers. It's conceivable that some kind of fraud has been perpetrated by a succession of tricksters... maybe they hid a set of induction motor coils under the water in the previous fall, ha-ha, but the bullets don't have to spin vertically. Some of them just lie there and spin on their sides.
But Mythbusters dug around up in a frozen lake in a snowstorm to verify it. They had difficulties, but they also reported it via video. I basically tend to trust Mythbusters:
Why trust them? Because they've got a good thing going with their experimentation, and I don't think they'd ruin that by perpetrating fraud.
As far as I can tell, there aren't many places in Hawaii where you yourselves could repeat these experiments.
Again, I had heard about this decades ago from a buddy of mine who said he had seen it happen with his own baby-blue eyes, and I thought he was putting me on, so I just let it go, even though there were occasional other reports of it I had read about.
However, repetition, even by "unqualified" observers, and even by "anecdotal" reports, makes me pretty damned sure I was wrong by not believing it in the first place.
After all, lets face it. At root, all science is ultimately based on initial anecdotes.
Maybe very cold ice
does act like a tough rubber sheet under high impact velocities.
In which case, maybe I'll invent a flak jacket made out of ice.

Terry, 230RN
AFTERTHOUGHT ON THE BULLET DEFORMATION QUESTION (Optional reading): Strange things do happen with high-velocity impacts. For example, did you ever wonder how come most of the craters on the moon are circular? It should be obvious that not all impacts come from directly above, or perpendicular to the moon's surface, yet the overwhelming majority of them are circular. Very few of them are oval or elliptical shapes, as may be expected from the number of objects hitting it at an angle.
The answer lies in the fact that the shock waves from the initial impact radiate outward in a circular (or shperical) pattern far faster than the speed of sound in the moon's material, so the crater formed is usually circular. Only objects hitting the moon at very low angles (I think it was 20° or less) form oval craters.
So it seems possible to me that the initial shock wave of the bullet's impact proceeds through the ice, shattering it in advance of the bullet's travel, forming a dense mush which slows it down quickly but without deforming it. After all, it's not like hitting a steel plate, where the tensile strengths of both the plate and the bullet are roughly equal. Just a theory. Which is why I think real physicists shuld be interested in the phenomenon.