Remote interviews are contextual inquiry sessions without the context. It is not as good as being there, but it is better than guessing or only talking to subject matter experts. We also have great tools to get closer to the participant without really being there. I use a phone line to ask questions and a WebEx Meeting so the participant can show me what they do with a specific software application or website. [I haven't been able to use Video yet, because most of my users don't have webcams.] WebEx does require some education for the participant. I usually send instructions for calling in and starting a WebEx session a week in advance. I also request that they go to the WebEx site before our interview to get the latest WebEx components.
A remote user interview starts off like most interviews, obtain some basic profile information and make sure they meet the selection criteria you have identified. Once you have the basics, ask questions that deal more with their job function and goals rather than their use of a specific tool. Allow the initial questions to personalize the interview when asking questions specific to the use of the tool, you can ask clarifying questions related to the users job function and whether the tool is helping them to meet the job goals they stated. It is important to have the participant show you how they use the tool to accomplish common tasks. I often start off by asking them how they get started, what is the first thing they do when opening up the tool. This usually gets them into the "instructor" mode, where they are teaching me what they do and sets a nice tone for the rest of the session.
Always end a session by thanking the participant and giving them additional contact information if they would like to follow-up with feedback. I encourage you to still use gratuities of some sort. I have found electronic gift certificates to be popular.