I've found that agile works if velocity is static and used for estimates ONLY and is flat over time. Once velocity is measured as an output metric and there is an attempt to improve it, you've just left agile and are now in a morass.

In the end, very simple Kanban is the way to go if your org can handle it.