I think the idea of augmenting the struts to maintain a linked list of elements together with periodically shrinking on removal would solve both time and space issues, right? 

Space will be always linear, and operations would still be constant amortized time (of course the worst case of removing will be linear because of the shrinking, but I guess this behavior is expected).

I wrote a worse example in bad_dict_example.py submitted to this issue.  This example would be fixed simply by the shrinking, but as is it's a pretty unexpected bug, as a simple sum(d.values()) can take milliseconds on a dictionary with only one entry (both key and value are int).