I experimented with different approaches last evening. Just changing the order of clearing the module dict does not help your first example, because the __main__ module is garbage collected, but its dict is not cleared. Adding _PyModule_ClearDict() in tp_dealloc and tp_clear helps with that example, but it causes several failures and crashes in tests. I have found issue7140 and issue18214 for not clearing module dicts.

So in conclusion, your approach may work. It clears dicts of all modules, but only at shutdown. It did not worked before, when the order of dicts was undetermined, but now we can utilize deterministic order of sys.modules and module dicts.