Is adding a(n empty) __init__.py file in each subdirectory considered to be too much overhead? After all, this is the only thing necessary to make Python interpret a directory as a Python package.

In fact, this is not necessary since Python 3.3, although this particular piece of misinformation has proven very persistent. In contemporary Python, recognition of "packages" is automatic. Adding an __init__.py file simply distinguishes a "regular package" from a "namespace package", which mandates that all the contents of the package are in the same subdirectory (namespace packages allow the package contents to be split across folders on disk). Some tools may also offer specific support for regular packages - but overall, the distinction is relatively subtle.

Aside from that, the problem isn't simply with recognizing that a folder represents a tree of Python modules - Python also has to be instructed to consider the root of that tree when looking for absolute imports.

I must admit that I shortly forgot about that, but it could be that the OP is actually using a Python version < 3.3 and is therefore having problems...