I think it's very important to ask an applicant to describe something on paper or with a whiteboard. Is he|she capable of explaining a concept in words and pictures or is he|she just a code wonk? This simple exercise separates out a lot of people who can sound smart but are just throwing up a screen of bs, and it's a critical skill in team environments.
Pick a task that has several levels of detail to describe and see how your applicant deals with it. For example,
- Describe how a 'little language' is handled.
- How does a webserver handle FORM scripts and their data?
- How does the Internet transmit data?
- Describe the process of creating a new program as a team effort.
You want to observe them as they do it. Do they launch in, do they think for a minute, do they spew nonsense for a while while gearing up to make sense? My interviews are typically more about how a programmer operates than they are about what he|she can or has done. It's easy to separate out the technical losers, but it's more important to assess how someone functions and where they fall short in the process of getting the job done.