I would think that rigid bodies -- either perfectly rigid or semi-rigid via springs & struts -- would not handle all that differently in verlet since force is explicit (typo on your part?) and a v/p estimate is available from the last position, albeit with a bit more phase lag than usual. Does the phase lag induce nasty oscillations or something?
I've played around a lot with Verlet, it is very powerful in certain cases...especially since you can just update the position of a mass directly (very easy to program, very mouse/touch input friendly). However, a rigid body physics engine is probably better for most game use cases.
Vehicle: http://apps.playcanvas.com/will/ammo/vehicle
FPS Character Controller: http://apps.playcanvas.com/playcanvas/physics/charactercontr...
Crates!: http://apps.playcanvas.com/will/ammo/crates
[1] Disclaimer: I'm a co-founder :-)