There will be plenty of good ideas added to this question. My personal experience has taught me that:
1~ The working product is a form of documentation itself: assuming the product is accepted, then asking what it should do under certain condition is equivalent to asking what does it actually do under those conditions - log in and try it to get your answer.
2~ The tests, be them manual or automated (or a mix), are a form of documentation. Certainly unit tests may be way too far from the domain language spoken by the less-technically inclined team members (eg: 'business Experts', or Customers). Acceptance tests may be closer to a 'middle ground' of sort. Definitely BDD-style tests seem to have the best chance to build a ubiquitous language everyone can understand (see in this regard Gojko's Bridging the Communication Gap). Nonetheless, all of these form of tests are a form of documentation which can be used to determine what the product should do.
3~ Depending on where your project falls on the spectrum, your documentation (and, in general, all your ancillary artifacts) may require a higher or lower degree of ceremony. Smaller products, smaller teams, where time to market is critical may find that a very formal documentation of requirement costs way too much compared to the value it adds. Extremely large projects, spanning multiple teams and years of development, on the other hand, will find the ROI of formal documentation quite different.
4~ In the perfect world, we probably wouldn't need to document requirements other than in the form of working code (which, in the ivory Tower would also be self-explanatory) and tests (mostly for regression testing, and -on the fringe- to drive development of new features). Thus, the question of requirements documentation is a question about what's different between the Perfect World/Ivory Tower and the Real World/Trenches. The answer, of course, is different on a case-by-case, depending on the project and the team. For instance, we could say "All requirements shall be kept into this wiki, and maintained with the utmost care, etc etc..." but if the team is not familiar and comfortable with wikis this would not work.
5~ In the end, the stakeholders are those you should ask. Certainly, the topic should be approached in a collaborative manner, because everyone on the team will have to interact with the requirements throughout the project, but you must find a form of documentation that satisfy the stakeholders' needs.
All that being said, here's some places I've seen requirements documented while applying Scrum (why do I feel like this word should always be followed by an asterisk?):
- PDF document
- Bulletin Boards
- Wiki
- Wiki + Automated Acceptance Tests (read: FitNesse)
- Unit tests
- Manual Test Plans
- User Stories, Use Cases diagrams (read: Enterprise Architect models)
- Whiteboards around the office
- Emails
- Post-it notes
And, to be honest, I cannot say that any one system has a consistently higher correlation with a successful project than the others. I guess, indeed, we don't have a silver bullet.
HTH, thanks for the thought-provoking question!