When the battery is pulled out during handset’s operation, it will instantly do a hard reset, so when this random reboots happened, it will basically hard reset your Sidekick. BGR reported that it could be caused by bad design on the battery and the battery contact.

You should either exchange the phone with a new unit (who knows you will get the same defective unit) or use a quick fix by putting a business card and stick it between the battery and the battery cover to give better contact to the battery connector.