Prototyping User Interfaces With Quality

A good user interface prototype is a powerful tool. It can be used to visualize/envision a concept/idea/design, discover design, experiment with different designs, test usability with real users, and lay the conceptual foundation for a product. It can also be used to engage and align stakeholders and achieve sponsorship and support for a project, e.g. funding.
Prototyping, of course, raises questions. What should be prototyped and how? If prototypes are considered throw-away, does quality matter? If so, what kind of quality should we aim for and how might we achieve it? And can prototyping be combined with agile approaches to software development, such as continuously delivering valuable software, emphasizing working software (through practices such as test-driven development) and simplicity (maximizing the amount of work not done)?