Android not killing activities from stack when memory is low

Calling finish() when you are starting the new activity will deallocate the one you are leaving. This will prevent you from accessing it with the back button, but it should keep memory down.

I was expecting the system to kill the oldest activities in the stack automatically BEFRORE the OutOfMemoryError was thrown

Android does not do this. Android terminates processes to free up system memory for other processes. It does not get involved with intra-app memory usage in a similar fashion.

How can we tell the Android OS that it is allowed to deallocate activities and its resources if needed so we don't get the "Unfortunately, your activity has stopped." dialog?

You can't.

Instead, you need to design your application to use fewer activities, or use fewer resources per activity. For example, you can "recycle" existing activity instances via FLAG_ACTIVITY_REORDER_TO_FRONT, or (as Mr. Tornquist pointed out), you can finish() activities manually yourself.

After playing for a while opening activities using the menu, the stack starts to grow and grow.

You should probably be using FLAG_ACTIVITY_REORDER_TO_FRONT on these menu items, so that you bring the existing activity forward in the task, rather than creating new ones each time.