Ask YC: How do you define application requirements, PRD?

My company used to develop applications following the waterfall model and we are now trying to move to Agile development. We have implemented a hosted Application Lifecycle Management tool (rallydev.com) which is geared around Agile development using stories.

We have been struggling to find the right balance between the old paradigm of creating lots of documentation up front (Market Requirements Document -> Product Requirements Document -> Functional Requirements, etc.) We also have a hard time determining where the documentation should reside. Should it all be in the stories themselves? What happens later when you are trying to understand the lifecycle of a feature, how do you figure out how it was initially conceived and how it has been modified over time? Would a wiki be a better place to track this evolution?

How do big software development companies develop their software for example, GMail or iMovie? Do they start with UI prototypes? Do they start with extensive market research and create all the documentation MRD, PRD, etc.? Frameworks like Rails push semi functional prototypes, but do those give enough information for development? Is more documentation needed? What tools do they use to track projects and the related software documentation?