I used to have the problem of my N800 randomly rebooting pretty often. I did 2 things, 1 or both of which helped quite a bit (not sure which did the trick since I did them at about the same time).

1. Try reseating your external memory card. Make sure it's ALL the way in. And that the door is completely closed.

2. If you are using your internal memory card as swap space, then try reformatting the internal memory card. Note that to have the N800 format it, it has to be mounted in the external slot at the time.

Hope these help. And yes, any time the device reboots, a huge chunk of battery life appears to be lost. Some of it "comes back" over time, but it seems that it really does drain some of the battery.