Hmm.  That might mean you need to do a big design change; while it often works, one really isn't supposed to rely on __del__ being called when a Python object first could be garbage-collected - when cycles are involved, Python doesn't even guarantee that it will ever call __del__.  It sounds like you'd be much better off with a named destructor-like method that would be called explicitly when you want to remove an object from the game.