Here on 32-bit Windows Vista, with Python 3:

C:\Python33>python.exe
Python 3.3.2 (v3.3.2:d047928ae3f6, May 16 2013, 00:03:43) [MSC v.1600 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> a = {}
>>> for k in range(1000000): a['a' * k] = k
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError
>>> del a

And here too Task Manager shows that Python has given back close to 2GB of memory.

>>> a = {}
>>> for k in range(100000): a['a' * k] = k
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

And here Task Manager shows that there's tons of memory still available.  sys._debugmallocstats() shows nothing odd after another "a = {}" - only 7 arenas are allocated, less than 2 MB.

Of course this has nothing to do with running in interactive mode.  Same thing happens in a program (catching MemoryError, etc).

So best guess is that Microsoft's allocators have gotten fatally fragmented, but I don't know how to confirm/refute that.

It would be good to get some reports from non-Windows 32-bit boxes.  If those are fine, then we can be "almost sure" it's a Microsoft problem.