I'd check the wire harness plugged into the VSS before I'd say the VSS was shot. Don't just check that the plug is plugged in securely; check the wiring too. I know Soundq had his wires to the TPS fray inside the insulation. The insulation frayed going to my coilpack, and then the wires started breaking and caused a 2 & 3 misfire.
Given the several times I've seen damaged wiring under the hood I'd say that this is much more likely a scenario than a faulty sensor. Usually when the VSS goes it just flat out goes. The hit-or-miss instability of the speed sensor tells me it could be a wiring problem.