I've just successfully installed GeoDjango and all the required libraries. I've set the environment variables and registry keys (yea working under Windows here) and everything works find from the command line.
d:\...\> python
>>> from django.contrib.gis.geos import *
>>> exit()
d:\...\> python manage.py runserver 0.0.0.0
(...)
Now when the server that's being run here encounters the very same line in code it's supposed to execute, it says
WindowsError at /NT/BUAConvex/4DED02804:SQLEXPRESS:44_EU_2011Q2/20187417/
[Error 126] The specified module could not be found
D:\...\views.py in <module>
from django.contrib.gis.geos import * ...
c:\python27\lib\site-packages\django\contrib\gis\geos\__init__.py in <module>
from django.contrib.gis.geos.geometry import GEOSGeometry, wkt_regex, hex_regex ...
c:\python27\lib\site-packages\django\contrib\gis\geos\geometry.py in <module>
from django.contrib.gis.geos.coordseq import GEOSCoordSeq ...
c:\python27\lib\site-packages\django\contrib\gis\geos\coordseq.py in <module>
from django.contrib.gis.geos.libgeos import CS_PTR ...
c:\python27\lib\site-packages\django\contrib\gis\geos\libgeos.py in <module>
lgeos = CDLL(lib_path) ...
c:\python27\lib\ctypes\__init__.py in __init__
self._handle = _dlopen(self._name, mode) ...
Thanks to @ed. and @g.d.d.c I found the solution. Problem turned up in the Django shell as well. Turns out I had set GEOS_LIBRARY_PATH = 'c:\OSGeo4W' in my Django settings where it should've been 'c:\OSGeo4W\bin'. Calling plain Python ignored those settings and instead relied on the OS-own functionality to find the .dll (which succeeds).