I believe this is an artifact of hash randomization which affects the order of how objects are destroyed during shutdown.  If you run your test using different values of the PYTHONHASHSEED environment variable, you'll probably see predictable results.  For example, with a particular build of Python 3.4.1, if I set PYTHONHASHSEED set to 0, thereby disabling hash randomization, I never see the warning:

PYTHONHASHSEED=0 python3.4 -W all test_warning.py

With it set to 1, I always see the warning.  With 2, no warning. With no PYTHONHASHSEED, I see random behavior similar to your results.

I don't think there is anything to be done here as Python makes no promises about when and in what order objects are collected.

https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHASHSEED