The link in the question had the answer (whoa... Zen). The location of arcgisscripting is defined in the Windows environment variable PYTHONPATH. By printing sys.path from a CGI script I could tell this was missing from the variables Apache was using. Easy fix: add this to httpd.conf:
SetEnv PYTHONPATH "c:/path/to/pythonpath"
Voilà, no more ImportError.