> Personally I'd prefer a new exception `StackOverflow` to `MemoryError`

+1 on a new exception (presumably a subclass of MemoryError).

How about using OverflowedStack instead?

The situation is not quite as bad as you suggest. Googling for "stack overflow" alone (with a space and no other qualifications):

* on Bing, scroll halfway down the first page of results to find the "People also ask..." 

  How do you get a stack overflow?
  How to prevent a stack overflow error?

* also on Bing at the bottom of the first page of results is a question on stackoverflow.com asking what causes memory stack overflows;

* on DuckDuckGo, the first page of search results fails to suggest anything useful;

* on Google itself, on the first page is the People Also Ask

  What causes stack overflows?

* as well as a link to Wikipedia's page on stack overflows.

I expect that going forward, "python stack overflow exception" will be sufficient to hit the Python docs somewhere on the first page.

Besides, presumably this OverflowedStack exception is likely to be rare, so I expect that few people will need to google it.