Interesting thread. I have a Garmin 60Cx that does (did) the same thing...random shut-offs due to vibration when I have it mounted on my bike. I don't use mine for training but for geocaching, so lost data isn't an issue, but it *is* annoying just the same.
I bent out the battery contacts inside the battery bay without taking the case apart. Also added a thin piece of foam to the inside of the battery cover to press on the batteries and keep them in place. Seems to be working fine now.