The solution is to call search.autodiscover() in the site's urls.py, in addition to having autoload and search in INSTALLED_APPS, as well as autoload.middleware.AutoloadMiddleware in MIDDLEWARE_CLASSES.
The reason is that while djangoappengine.views.warmup and djangoappengine.deferred.handler.application load INSTALLED_APPS and result in search.autodiscover() being called, djangoappengine.main.application does not does not do that. So if your GAE instance is fired up directly by a request, then the search indexes will not be registered. Therefore, search.autodiscover() in urls.py is necessary to register those indexes.