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.

The link in the question had the answer... 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"

And no more ImportError!