Don't get freaked out, remember the majority of people who post to the Internet post with negative experiences; there are a lot more people who never post anything who have great experiences.
The one where they never even removed the screen protector was clearly an anomaly and not the norm.
Having had to do this a few times myself (not a Droid yet, but a couple LG Voyagers and a BB), and talked to many people on the web who have had experience doing so, here are my tips
1. NEVER EVER get a replacement from the store. Always call CS and have them mail you one. Takes linger but less likely to get a faulty one
2. Look the phone over very carefully, turn it on check for other customer data etc (never had this problem, but good to check anyway), check the sticker on the back where the ESN is and make sure they did not pit one sticker over another.
3. As for the "certified like new" sticker on the screen, not all refurbs have this and I have actually had better experiences with ones that did not say that specifically (all come in plain brown boxes)
4 VZW Policy: If you have had the phone less than 30 days you are entitled to a NEW (as in retail box) replacement, INSIST ON IT
5. VZW Policy: If you have had the same phone replaced 3x in 90 days then you are also entitled to a NEW phone or to swap for a different model (again push this since some reps don't want to honor it)
1. I would not trust an out of the box phone more than the ones from the store as they are probably the same thing. From different posts, the Droids refurbs from either mail and store appear the same in regard to appearance and packaging. One person received a refurb in the mail with a screen protector from a previous owner on it, so mail refurbs are not guarantees.
2. I would also assume all new refurbs even those mailed have a sticker over the ESN original as these are refurbs.
5. I wish I knew about that policy as I would have brand new phone rigt now. Of course they might argue two of the exchanges would not count as the rep did not feel some of the hardware issues I experienced were serious (dust under screen, clicking when touching screen, etc.). But, my current refurb is working great, doesn't click to touch, and appears to be built solid with the touch screen component perfectly up against the manual keyboard.