homepage

The attached unit test fails with an ImportError... sometimes. Here's a little blob of shell that seems to make the failure come up more quickly:
while ~/Projects/cpython/3.3/python -m unittest -v test_broken_import; do
 rm -rf test_broken_import;
 rm -rf __pycache__/;
done
An example of the output when I run it:
exarkun@top:/tmp$ while ~/Projects/cpython/3.3/python -m unittest -v test_broken_import_minimal; do rm -rf test_broken_import; rm -rf __pycache__/; done
test_renamedSource (test_broken_import_minimal.BrokenTests) ... ok
----------------------------------------------------------------------
Ran 1 test in 0.004s
OK
test_renamedSource (test_broken_import_minimal.BrokenTests) ... ok
----------------------------------------------------------------------
Ran 1 test in 0.005s
OK
test_renamedSource (test_broken_import_minimal.BrokenTests) ... > /tmp/test_broken_import_minimal.py(53)test_renamedSource()
-> print(e)
(Pdb) c
No module named 'twisted_renamed_helper'
ERROR
======================================================================
ERROR: test_renamedSource (test_broken_import_minimal.BrokenTests)
----------------------------------------------------------------------
Traceback (most recent call last):
 File "./test_broken_import_minimal.py", line 50, in test_renamedSource
 from twisted_renamed_helper import module
ImportError: No module named 'twisted_renamed_helper'
----------------------------------------------------------------------
Ran 1 test in 0.759s
FAILED (errors=1)

The FileFinder class (a "path entry finder") uses a cache to efficiently track changes to files. You can manually clear this cache by calling importlib.invalidate_caches(). The Python test suite has several examples of clearing the FileFinder cache in this way.
I've verified the failure as described. Using importlib.invalidate_caches() at the spot where the script cleans up sys.modules, the failure goes away.
Depending on OS filesystem timestamp resolution, you could see the behavior just as you've described it. Since normally you wouldn't remove and re-add modules like this, it isn't normally an issue.

Thinking about it, it may be worth adding a note to the docs for sys.modules making it clear about importlib.invalidate_caches(). I'll see about writing up a patch when I get a chance.

I don't think sys.modules is the right place about a warning regarding importlib.invalidate_caches(); this has nothing to do with sys.modules but instead import itself. Probably something more along those lines would be more fitting.
This is also mentioned the 3.3 What's New on how to port your code, so at least that's covered.

The relationship between invalidate_caches() and sys.modules is definitely tenuous. However, my rationale was that people would look for an explanation on why modifying sys.modules was not working as expected. The sys.modules doc entry was the one that seemed to make the most sense. 
However, this is a pretty uncommon case and you're right that the What's New entry should be enough.