This is a problem many collision systems encounter. The usual solution is to ensure you check often enough that you do not miss a collision. Slow things down, or speed up the rate of your checks.
The latter is in theory straightforward, you just run your dynamics system at e.g. 2x the frame rate. With everything moving only half as far you are much more able to catch collisions. Only every other frame is passed to the renderer, which is normally the most expensive part of your app (including on the CPU).
2x is a good starting point, but you could go higher to 3x or more if necessary. Or just slow down your objects so all collisions are caught at 2x.