The basic problem here is that, like many physics solvers, mine determines all the intersections in the scene, and then attempts to simplify the equations involved by partitioning the physical scene into as many independently solvable "islands" as it can. While this works quite well for nice slow moving things like characters - a single speeding bullet can break both of these steps. Firstly, just testing for collisions at a single point in time per frame will miss many intersections along the path of motion for each frame; and secondly once you start detecting the intra-frame intersections, introducing these inside a simulation step forces you to recalculate the islands, which in turn invalidates any simulation that's already occured on any of the effected islands.
I wrestled uselessly with a few designs for mixing event-driven simulation with the LCP solver based on the swept volume intersection - but I quickly started to feel uneasy when I realised how much damage this could do to the stability of the existing solver, and how much complexity it would add to an already very complicated piece of code. I kept thinking there just had to be a way to fit high-speed object simulation into the existing simulation framework so that all of the existing constraints and options would work seamlessly with bullets ... and then it dawned on me: rather than trying to bend the physics solver to handle the timing of the bullet, I could bend the timing of the bullet to fit the physics iteration!
It's exactly 10 lines of code and it seems to work a treat so far. I just cast a ray out along the trajectory of the bullet before doing the normal collision pass, and if I find something, I just pick the bullet up and move it to make sure the physics simulation sees and handles the collision. It does subtly change the timing of the bullet, but given it's about to bounce/blowup something anyway, I doubt you'd ever really notice it. Here's a small video of it in action: