I originally thought that maybe httpd should be a symlink to lshttpd, but that's definitely not true lshttpd is already running! I then got a complaint that one of our CGI's wasn't running. I noticed that lscgid wasn't running. So I got the hunch of symlinkning lscgid to httpd. Sure enough, that fixed the problem!
So the question is on Solaris, why is lshttpd trying to exec() lscgid as 'httpd'?