What do bullet trails really look like?

In reality, it is possible to "(almost) freeze time" and examine such phenomena, through the use of high speed photography. The fact that no clear photographs of "bullet trails" are readily found is a good indicator that such phenomena are not readily produced or observed. That said, there are two effects I can think of that could in principle lead to visible phenomena in your case of interest. They are both mentioned below, but the short answer is that neither will typically be "visible" in any reasonable sense of the word for a projectile the size of a bullet.

In the right regime ($M \approx 1$), the Prandtl-Glauert singularity can lead to condensation, producing a visible cone of condensed water vapor [gallery],[discussion]. The characteristic scale of this cloud is the same as that of the object. In this case, that means we are talking about a "cloud" of water vapor on the scale of a few $cm^3$. It is highly doubtful this effect would be readily visible for a projectile the size of a typical bullet, but nevertheless it could be present, given the appropriate conditions.

photo credit: Ensign John Gay, USS Constellation, US Navy

The second phenomena that could potentially be visually observed is distortion/refraction due to the changing density of air. I believe this is the effect present in the video clips you linked. This will visually act like a mirage (arising from the same physical cause, spatial variation of fluid density and therefore index of refraction), and it's visibility will depend significantly on illumination conditions and observational geometry. It doesn't "look like" anything, but rather distorts the path of light rays passing through it. It can be made much more readily apparent in controlled conditions as in this shadowgraph:

photo credit: Andrew Davidhazy

Surely the simplest thing to do is google for some images...

In particular several of the images on the bottom half of www.digitalpicturezone.com/digital-pictures/30-colorful-examples-of-high-speed-bullet-photography/ show a non-trivial stretch of space before the bullet's point of impact. You'll notice a marked lack of The Matrix-like effects.