Definitely go to a "real" VZW store. The "authorized dealers" don't have anything to gain by giving you a cheap (expensive) phone.
I like "Lookout Mobile Security". It lets you see your phones GPS location, uploads any pics taken with the phone every day at a time that you choose, and you can tell the phone to make a loud high pitch noise. Should be enough to find it.
Just an idea for your next phone.