My initial reaction to the question leads me to believe that an exchange between yourself and the client does not...
happen on a regular basis.
Make it part of your "process" to involve the client at every step of the way. Finding out something cannot be done late in the delivery cycle is more painful than finding out shortly after seeing the initial prototype. If you can work with your client in a more agile fashion, you can make many small changes and tradeoffs more often, fine tuning the implementation as you go along. Before either of you know it the feature will be done, and there will not be any shock that it does not meet expectations.
Another way to help with this problem might be to focus more on the value that your client wants to achieve from some particular feature, rather than the implementation (prototype). Consider capturing the requirements in the form of user stories or use cases, each with a clear goal or expected end result. Make sure your client agrees with those expected results. This helps to direct the focus of requirements validation away from the specific implementation details and onto the end result. The downside to a prototype is that if the end product does not look just like the prototype the client may see that as a failure, or view it as incomplete, even if the desired goal is achieved. A mix of both prototypes and stories or use cases is probably necessary; just don't expect to capture all of the requirements in a prototype.
Being agile is not to say that you do not need to understand the big picture early on, it is not an excuse for ignoring things such as performance or architecture requirements that must typically be built in from the very beginning. However, for either you or the client to understand and document "all" of the requirements up front is not realistic. Have regular conversations, make decisions and tradeoffs on a regular basis, and hopefully you can avoid delivering a sudden surprise to your client, when it does not turn out just like the recipe said it would.