I had the same thing happen today with a VistaHCx I just got. I loaded a bunch of caches into it last night. All seemed good. Playing around with it, I deleted a couple that I had already found.
Today, I got out to an area I was hoping to do a little caching, and all the caches and other waypoints I had were gone.
I looked through all the menus and could not find any way to intentionally delete all.
I'm thinking this Garmin might be going back to REI.