Are you using php-fpm or spawn-fcgi? From my test, the former performs better under heavy load (though I am not sure since I tested it with nginx, not lighttpd; tested with apachebench with wordpress installation)
fcgi, however the number of requests per second was fairly modest really, so I doubt that type of overhead was the issue. More likely something on the MediaWiki side was being inefficient on the particular pages being spidered I think.
Yay for speedups! :D
I did some tweaking to the server configuration... according to benchmarks I improved things so that Main_Page went from 5.41 requests/second, all the way up to 80.71 requests/second.
Special:RecentChanges improved less though, going from 2.26 requests/second to 3.44 requests/second.