I've had similar difficulties using batteries. Sometimes it would not power up (especially after swapping the batteries), or else it would intermittently reboot when moved. As near as I can make out, it's the little red plastic tabs that separate the battery contacts from the adjacent ones, at either end of the battery compartment. Mine seems to have gotten a bit bent or twisted over the years of removing and inserting batteries, trying to pry them up with my fingernail. This probably pushes the positive battery terminals away from the contacts.
Some battery brands have very slightly different caps on the positive terminals, and that may make a difference. My solution was to stick a few layers of thin cardboard, say, the thickness of two or three business cards, or two strips cut from a cereal box, on top of the batteries just before sliding the battery compartment cover back on. I guess it presses down on the sides of the batteries and keeps them seated in place better. Now that I think of it, I should just scotch tape it to the inside of the battery compartment cover.
I'm sometimes tempted to just clip the bent parts of the loose tabs off, but that's an irreversible thing, and it may mess up the isolation between the terminals.