The user story format is pretty flexible.
“As a (type of user), I want (some goal) so that (some reason)”
I've seen this format used successfully at my workplace. For example:
"As a System Administrator, I want copies of the product catalog sent daily to our Sales Partners so that these partners always have the most current version of our product catalog"
In this example:
A feature is defined. The feature might take the name Partner Extract, for instance. It might be implemented as an ETL job that runs nightly to create data files that are made available to Sales Partners via SFTP.
The user story embeds the roles. The two roles identified are System Administrator and Sales Partner.
Incorporating non-functional requirements is easy. The above example includes one non-functional requirement: the product catalog updates must be daily. Requirements that address how much, how fast or how often are non-functional requirements. I like to refer to these requirements as "quality attributes". Here is another example of a user story that expresses a quality attribute:
As a Call Center Representative, I want customer search to return the result in 2 seconds or less (on average) so that customers are not left waiting on the phone.
Write user stories for reliability, security, capacity or any other quality that is deemed important.
Feature Dependencies
You have identified some legitimate limitations of user stories. They are unordered and there is no guarantee they will be independent. In fact, the might be interdependent-- a chicken-and-egg problem. I believe that all non-trivial projects require documentation to supplement the user stories. I watched the agile team here at work create activity diagrams (flow charts) of the business process. These diagrams were used to analyze the feature dependencies. Another approach might be to create [PERT diagram][1] in a big all-day session with the customer. In the end, some other artifacts will be necessary to support the user stories.
Epic!
A narrative that describes the scope of a project is a good idea. There should be something like a [statement-of-work][2] or a [project charter][3]. No serious project should be without one. These documents provide a starting place for identifying user stories. These document help answer tough questions like "What should be the priority of this feature?"
Metadata
After 15 years in the business, I have an opinion about meta-data. In general, it should be avoided. A few reasons include: after a month, no one knows if it is accurate; no one knows if it was updated; it is extra work to create it; you can't predict what metadata will be useful. Most meta-data is a distraction. I like to track owner, author, priority, estimate of effort, and date of last modification. Beyond that, I fight hard to keep meta-data out user stories and use cases.
Benefits (so that...)
I have an opinion about this as well. :-) Including the benefits is vital. Often, users will request a feature without having though about its value. No matter how good an agile team is, the project will fail if it implements unimportant stuff at the expense of more critical functionality. Also as a developer, I do a better job coding a feature if I know how it fits into the big picture. Here is a real-life example of a requirement without justification: "*The system shall prevent transactions with EIP and a gift card from occurring.*". Huh? What is EIP? Why do I care? Why does anyone care? I don't know. Understanding the context would have been helpful before I went to the business analyst for clarification.
Even worse is when no one remembers why the user story was written. Do we still need this one? Has the business process evolved to the point where this user story is invalid? Does anyone know? These conservations waste time. It gets suckier if the the author of the user story has left the company.
Measurement
Here is an example of user story that is not measurable:
As a Call Center Representative, I want the system to be fast so that customers are not left waiting on the phone.
How fast is fast? A millisecond? A tenth of a second? Ten seconds? Nobody knows. Nobody wants to be wrong so no one every even makes a guess.
Compare that user story to this one:
As a Call Center Representative, I want customer search to return the results in 2 seconds or less (for average daytime call volumes) so that customers are not left waiting on the phone.
This user story is testable. Average day time call volume can be determined from log files. Performance testing can be conducted to determine if the requirement has been met. Even better, the users and developers have agreed on the success criteria well in advance of the end of the project. Testable requirements are a beautiful thing.
