proxies -- somebody in the company who represents the users

  * sometimes works well, sometimes works badly.  The proxy is probably not going to be exactly for your users.

  * these people are usable only for a short time because they become experienced users very quickly

Usability

  * user tests

  * user profile

  * log analysis (for applications that do logging, such as websites, help desk logs)

There is rarely any such thing as a "training issue" unless the training issue is with the user not really knowing eir own domain.

Identify and find your stakeholders.  Immediately start getting feedback from them.  One person was saying that Agile developments are getting a little too fast-and-loose with this step.

Also, how can you define what you are really looking for when there are conflicting requirements from different stakeholders?

When asking for users for a usability study, offer some kind of gratuity.  Apparently current standard gratuity is between $80 and $150.  Sometimes, though, this can cause some legal issues, so watch out for those.

Usability references:

Jacob Neilson and Neilson Norman Group