I think your point might be the missing piece. Agile might not mix too well with fixed timeframes or fixed budgets, but rather needs an environment of continuous development where the requirements have room to drive the project within wide enough budgetary boundaries.
This to me feels sort of a natural way to build things. If we need something we build it, otherwise we don't. And those "needs" might pop up at any time, by external (customer requests etc.) or internal (new techical requirements become apparent as the project is being developed) events.
My experiences of agile development have been from companies without deadlines and are generally positive.