If this is with the factory VSM system, you may have a problem with the VSM itself, or a relay like you said. Think about it, when you press the unlock button once, driver door unlocks. Second time unlocks all four. So my theroy is that it has two seprate relays or contacts. One to actuate the drivers, and the other to actuate all four.