Inconsistent collision detection on slow-moving objects

I'm using a gun to shoot spheres that stick to the floor. The spheres are moved using Unity's rigidbody code (i.e. I simply set the rigidbody's velocity when fired). When the sphere's collider intersects the floor's collider, the sphere is immediately halted. However, the collision is detected later than expected, and as a result the spheres intersect the floor at varying depths (see the image below). I would expect a problem like this to occur with fast objects, however these spheres are moving quite slowly, and I could swear I've never had a problem like this with slow moving objects before.

I have tried setting their rigidbodies to continuous dynamic while firing them at a continuous object, to no avail. Reducing the physics timestep to around 0.005 (from 0.02) DOES alleviate the issue quite well, but doing 4x the usual physics steps feels a bit heavy. Surely with the default physics step of 0.02 there shouldn't be as bad a problem as what I'm currently having.