Why do I need to remove my battery periodically to fix phone problems? On my HTC MyTouch 4G (Android 2.3.4), twice now the diagnosis for odd failures was to take the battery out, wait a minute, and replace it.  (The first failure was loss of network; the second was web sites only partially working, e.g. I could read SE sites but not log in.)  Both times popping the battery fixed it, and my provider told me I should do this every couple months as "preventative maintenance".  This violates my mental model.  So, clearly, either my mental model is wrong or HTC and the folks at T-Mobile are having fun with me.  I'm going to start by assuming it's the former.

I power the phone down at least once a week.  I think of this as being like rebooting a laptop computer; when it's powered down I don't expect the battery to be retaining any state.  But if that's true, why does performance degrade over time?  What is my phone doing with its battery during these times?  Does periodically powering down do anything useful, like kill long-running processes?

I tried Google and reviwed the "battery" questions here before asking.
It's not the battery retaining state, it's the phone circuitry retaining state. Even when you use a "power off" command and your phone looks powered off some of the circuits will still be connected to the battery so that the phone can be turned on by just pressing the button. So there will be some circuitry powered on even after the phone was "powered off".

This is likely a bug in the circuitry. This actually happens to devices - you sometimes need to "power cycle" them by unplugging them from the power source and then plugging them back. In case of a mobile phone that requires removing and then installing the battery.