My experience: I've been through 6 Droids in the past 2 months. My first (and original) had a problem with the headphone jack shorting out after 4 months of use. Verizon sent me a "Certified Like-New Replacement" which is basically this: Verizon take all of our problem phones that we send back and sends them to a 3rd party refurbishing firm. The 3rd party refurbisher sends the phone back to Verizon, and they send them out as "Certified Like-New Replacements."
To continue my phone story, Verizon sent me a refurbished phone. This one was put together rather shabby, and had a piece of foam jetting out from the side of the screen. I sent it back, and they sent me another one. This one had the screen inserted crooked, so I sent that one back. Got another one, and the proximity sensor was faulty and would just the screen completely off while in a call. Got another one from the Verizon store this time so I could visually inspect it before I left. All seemed OK until I got home and noticed that a screw on the back side of the screen was lose, and scratching the heck out of the keyboard. Sent it back and finally got one that seems to work perfectly and have no issues.
My advice, there's no other alternative besides going through Verizon. Their "Certified Like-New Replacements" are pretty shotty, but hang in there, and you should get a decent one eventually. If you are really having trouble, and you have insurance, drop it in a bucket of water, or run it over with your car, pay the $89 and get a brand new one from Asurion. Unfortunately, you'll never get a new one from Verizon.