So much chaos: A day later I try the most recent code I posted above, and the app would load and instantly quit (similar to what was happening to Jesse Scott in his post above). Then re-presenting the sketch to the phone stopped this behavior. So I have no idea what's going on there. But it did prompt more research ;)
Found some interesting things by making a simple sketch that would print when it was in setup(), draw(), and the parent Activity's onPause(), and onResume():
When a sketch is started (for the first time) it goes through these states:
onResume()
setup()
draw()
Now, if you press the back button to exit, the sketch exist immediately, bypassing onPause (& onStop(), & onDestroy()... it just 'exits'). But the sketch physically removes itself from memory that way, which is what I want.
If you press the home button instead to exit, it does exit through onPause(). However, checking DDMS, the sketch is still running in memory. And if you then restart it, you run into the issues mentioned above where the sketch won't display its graphics: It re-enters in onResume(), but setup() and draw() are never called, and my guess is because the sketch is still in memory. This can be solved by embedding redraw() in onResume() which kicks the sketch in-gear, but this doesn't solve the issue of the sketch exiting properly from memory.
The System.exit(0); call in onPause() seemed to work for a while, but I ran into the endless loop of open\quit, so scratch that.
Based on a__g's suggestion I tried embedding finish() in onPause() (which again, is called by pressing the home button): The app still won't exit from memory, but it will restart properly, emulating the effect of embedding redraw(). Interesting. I also tried adding the noHistory attr to the AndroidManifest.xml file for that sketch, but it had no effect.
Sooooo, I finally went back to ckamath's post above using the onUserLeaveHint() & onDestroy() pairing, implementing them exactly has he has done, and everything works great: Pressing the back button exits the sketch & memory immediately (like it always has), and pressing the home button calls to onDestroy() which is overridden with System.exit(0), which then closes the sketch & memory as well. And everything restarts properly as it should (I should have just stuck with that method to begin with ;-) ). The interesting side effect with this technique is that onPause() is never entered, since the back button skips it, and the home button, which used to call to it, is now overridden to call directly to onDestroy(). Nothing wrong with that, but worth noting. The other thing worth noting is that calling System.exit(0) in onDestroy() appears preferable to calling to it in onPause() (due to that open\close loop problem I encountered).
My only fear is that when I try this same code tomorrow, it will behave differently again, which seems to be a theme with this specific troubleshooting process :-)
So hey big Processing brains, maybe just setup the back end to hand this for the user so they never have to? :-)