Should we always follow the story approach? What if the nature of the beast is that there is a continuously evolving application where one cannot define even a functional test with data? If you define a story, no sooner than its 'complete', it will need to be changed, since new information comes along that makes your acceptance criteria obsolete.
Since I am currently experiencing such an approach in a particular area of the project I work in, we are veering round to the view that we need not track velocity or story completion of such work. For purposes of documentation, we will still have stories which detail what work needs to be done at a point of time, but we are not going to bother with tracking the acceptance criteria after that and the points delivered once this work is complete.