1: This problem is also discussed in this thread:
http://www.samsunggalaxysforum.com/media-problems/battery-removal-cause-configuration-lost-and-applications-stopped-unexpectedly/I have a post over there with info that I'll not repeat here.

2: Let's call this problem the "packages.xml permissions problem."

3: The battery has nothing to do with it. It's a bug in Android.

4: If you get stuck in a loop you can hold down the "home" key to get to the task manager and from there you have some control.

5: NOTICE: The script reproduced in this thread is a little old, it's been modified and improved since then and has some enhancements specifically for the Galaxy S. Here's an updated version (v1.4E):
http://pastebin.com/rLWduRWc 
Let's all give a big round of applause (including from me because he got me going) to FlorentBL for posting that script. The script also worked for me. However FlorentBL is such a genius that it's difficult for him to understand arsenic's newbieness, so I've written some expanded instructions.

The code that you see is a Linux shell script, which means that it's like an old DOS batch file. You might think that such batch files are old fashioned but they aren't. Especially in Linux, scripts like this are a main way of doing things and the UNIX scripting language is awesomely powerful in contrast to the old klunky DOS scripting, which was written by one guy in his spare time after work and on weekends. To run the script, you'll need to copy/paste the code into a text file and save it on your SD card, and then run it. To run it you have to go to a command prompt and run it from there with a command. Otherwise there is an app called "GScript Lite" that will browse to the script and run it. I hope the following comments will help you, I suggest that you copy the comments into the script and save them with the script for future reference, when you have the problem AGAIN!

I tried to copy/paste the script from this thread while working on my phone, but I was not able to do that so I had to use the computer to make the file and then transfer it over. The "pastebin" link that I referenced up above might help you if you are working on your phone.

# This script is needed when the packages.xml file gets corrupted on the phone
# (happens from time to time) and Android tries to rebuild it and gets the permissions
# wrong. Symptoms are: Apps suddenly start crashing after a reboot,
# apps can't save their settings, apps lose data. The problem is that the apps lose
# permission to get at their data stores. This script scans the packages.xml file,
# ferrets out the userID for each app as well as the location of its data store folder,
# and than sets permission on the data folder to allow the app's UserID to have access.
# The script uses busybox (both implicitly and explicitly) and needs BusyBox v1.19
# (which is the first version to support the "cut" command). The script looked for
# packages.xml in /dbdata/system, but on my Samsung Galaxy S Epic it was found in
# /data/system instead, so I had to edit that path in the script.
# Remember that Linux is exhaustively case sensitive, so if you have Packages.xml in the
# script when you need packages.xml, it won't work.
# You'll need most or all of the following things: root, a text editor app,
# a file manager app,
# BusyBox v1.19 or later, BusyBox Installer (the only way to get BusyBox v1.19), some way to transfer
# files from your computer to your phone (like a USB cable or an ftp server on your phone-I use SwifTP - it's awesome),
# and either GScript Lite or a "terminal emulator" app.
# The script needs super-user (su) access, so your phone will need to be rooted. There's
# no downside to rooting your phone, so just do it BEFORE you get hosed by this problem.
# If you have been asking for the last
# year "Why would I need to root my phone?" here ya go.
# You can launch the script from the Android GUI by downloading and using app GScript Lite,
# or you can launch it from the Android command line by downloading a so-called
# "terminal emulator" app (which may be the right name technically but it's really just a
# "command line interface" app), and then entering the following four commands on the
# command line (you have to hit "return" on the keyboard after you enter each command to
# make it execute):
# -----------------------------
# $ su
# # cd /mnt/sdcard/
# # pwd
# # sh ./permfixer.sh
# -----------------------------
# Those commands assume that you saved the "permfixer.sh" file in the root folder of
# your SD card.
# In the above commands, on each line, ignore the first # sign, don't type it on the
# command line, that's just a comment character that has to be the first character of
# all these comment lines in this script. The second character (either $ or #) is the
# Linux command line prompt, the $ is the normal Linux command line prompt, so you don't
# type that $ or # either. The "su" command means "switch to super-user," and if it works
# Linux will switch the prompt from a $ to a # to remind you that you are in super-user
# mode, that's why the other three lines start with a # prompt. The "cd" command means
# "change working directory" and changes it so that you are working at the root folder of
# your SD card. If that line does not work for you, you may have to change the "/mnt/sdcard"
# path (which worked for me) to something else. The "pwd" command means
# "print working directory" and will print out your current working directory, which will
# allow you to verify that the "cd" command you entered worked properly. The "sh" command
# means "Linux shell" and will cause Linux to execute the script file. The "./" in that
# line means that the script will be found in the current working directory, without that
# Linux failed to find the script for me.
# So nutshell instructions for a rooted phone are:
# Use your computer to copy the script into a text file using Notepad.
# Save the Notepad file to your computer
# transfer the file to your phone's SD card.
# download and install GScript Lite.
# Use Gscript Lite to browse to the script on your phone and run it.
# The script will print interesting info that you can read and decide if it worked or not.
# Repeat efforts until it works