> Classes written in C are necessarily thread-safe (they rely on the GIL)

That's not really true. A single Py_DECREF() can release the GIL by way of executing a Python __del__ method (or a weakref callback, or even the tp_dealloc of a file object that happens to release the GIL when close()ing the underlying file descriptor) somewhere along the reference chain, as evidenced by Amaury in http://bugs.python.org/issue15320#msg165253

I think that if the deque documentation makes the claim that some methods are thread-safe, they should be *really* thread-safe (which doesn't necessarily imply a lock, but implies being extra careful). Otherwise it's better to remove the claim from the docs.