This definitely should not happen. It sounds like the backup battery has died-- it maintains your data for approximately 10 minutes when the main battery is removed. As a workaround, you might try connecting power to the PDA before pulling the battery.
-------------------- Lisa Gade Editor in Chief, MobileTechReview