Also, a verlet-based physics engine is a very different beast compared to a rigid-body one (a few in the list above are also based on verlet, but not most).
Verlet integration uses an object's change in position at time t to determine the velocity for t+1- it is typically used for particles not full rigid bodies.
Verlet is incredibly stable and allows you to update the position of a mass directly (velocity, force, momentum are all implicit), making it very easy to work with if not very accurate. You can't emulate rigid bodies very well (shape matching kinda works), collision response and stacking is a pain in the ass.
I guess I'm still having trouble understanding where the complexities arise. I have no difficulty believing that they do arise, but I would like to understand how it happens if you're willing to take the time to explain.
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?
We can make semi-rigid bodies in verlet using strings are shape matching techniques, but the pressure needed to maintain shape necessarily interferes with stacking or any other kind of stable contact. Actually, their was a solution to this in a shape matching paper by Matthias [1] but I was never able to get it to work right.
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.
[1] https://github.com/soulwire/Coffee-Physics