Our worst experiences have come when the clients had no clue what their use case requirements are -- and we have learned that the hard way. Any insights you have are valuable.
The only format I can recommend is one that allows you to collectively come to agreement about the requirements and allows you to effectively "sign off" on the requirements. Whether those requirements are for an iteration or sprint, or for an entire project, everyone needs to be able to agree on the set of requirements.
In terms of format I do find that any time the requirements are completely documented in a textual format, (read: very long document) there are disagreements or misunderstandings later about how the requirements should have been implemented. Complementing the requirements with some type of a visual goes a long way towards gaining acceptance and understanding. This could be a simple scenario diagram walking the user through the steps of a use case; or maybe even a basic prototype or wireframe. If your prospect/client has to read a long document without any visual aids, I bet there will be confusion later. You'll have to determine the visual method that works best for your prospects/clients, and it may take more time up front to build these visuals, but you will save time later.
The issue that strikes me as more important is how to help draw out the requirements from those clients that don't know what their use cases are. It is not uncommon at all that asking a user what they want will elicit a response with lots of ideas, most of which are incomplete and would not qualify as a good "requirement" by any formal definition. Requirements management is part science and part art. The science part is writing down the requirements, or using a requirements management tool. The artful part is teasing out the details of what the user really wants. It's differentiating between what they want versus what they need and which items will translate into revenue. A quick search for "requirements elicitation" on Amazon.com yields several decent books on the topic. Building your interviewing skills will help you capture the important set of requirements, instead of gathering all of the requirements.