There are two sides to this. First is verifying the identity of the user, and the other is verifying the legitimacy of the help desk. This is a pretty big deal because social engineering calls will almost always be directed toward the helpdesk or be impersonating a help desk member.
Since normal users are typically less sophisticated than help desk operators, you should simplify the process for authenticating the help desk. For example, a very easy rule is all help calls must be made from the user to the help desk. If the help desk calls you, then their only instruction should be "call me back at the standard internal help desk phone number". At no point should you trust a help desk rep who called you. This is easy for people to remember, and easy for them to implement. Also, whenever does call a user and says "call me back" it would be a good idea to remind him why he should do so; just a word or to so the concept is fresh on his mind: help desk ALWAYS tells you to call them back.
Then, authenticating the user with the help desk depends on the level of security required by the company. A "call in PIN" or password is a reasonable but not wonderful idea. Even better is some sort of internal closed-loop system that can't be made available to someone outside the company.
Better still, simply make the rule that all sensitive operations must be done in person, either at the help desk itself or through desk-side support, with appropriate checking of badges etc.