Okay, I found it.  sys.settrace() ultimately results in the setting of tstate->use_tracing to true and sets tstate->c_tracefunc and tstate_c_traceobj (see sys_settrace() in Python/sysmodule.c and PyEval_SetTrace() in Python/ceval.c).  tstate->c_tracefunc() gets set to trace_trampoline() in Python/sysmodule.c and tstate->c_traceobj gets set to your tracing function.

When an execution frame begins, the interpreter sets up tracing.  From Python/ceval.c:1124:

/* tstate->c_tracefunc, if defined, is a
   function that will be called on *every* entry
   to a code block.  Its return value, if not
   None, is a function that will be called at
   the start of each executed line of code.
   (Actually, the function must return itself
   in order to continue tracing.)  The trace
   functions are called with three arguments:
   a pointer to the current frame, a string
   indicating why the function is called, and
   an argument which depends on the situation.
   The global trace function is also called
   whenever an exception is detected. */

So trace_trampoline() gets at the start of each block and once for each line of Python code.  Each time it calls call_trampoline() (also in Python/sysmodule.c).  You'll find that in call_trampoline(), there is a call to PyFrame_FastToLocals() just before it calls your tracing function (at that point called "callback").

When called, PyFrame_FastToLocals() updates the contents of the frame's "slow" locals (f_locals) with the values in the fast locals.  And...wait for it...f_locals is the dict that gets returned by locals().

Thus, when tracing is on, the dict returned by locals() gets updated once per block and once per line of Python code.  That is exactly what you are seeing.

When tracing is not on, PyFrame_FastToLocals() would only be called when you call locals() (inside a function).  It's interesting to note that in that case locals() will return the exact same dictionary:

>>> def f():
...     return locals() is locals()
...
>>> f()
True

Conclusion
----------

The bottom line is that the docs for locals() could stand to have a little more detail for this case (including a link to the docs for tracing at sys.settrace() or wherever).  However, the behavior here is--at present--a CPython implementation detail.  Any note would likely say as much; something like this:

.. function:: locals()

   ...

   Each call to locals() will return the same dictionary, updated to
   the contents of the current local symbol table.

   .. impl-detail::

      Under tracing and profiling in CPython, the dict returned by
      ``locals()`` will be updated at the beginning of each code block
      and at each line of code.  See :func:`sys.settrace`.

The note is really only meaningful for functions since class bodies and modules don't use fast locals and f_locals is set to f_globals (i.e. locals() == globals()).  However, that point is superfluous to the above note since it remains true either way.