I found few url-rewrite based solution for enabling Permalinks in Wordpress+Lighttpd but none of them worked flawlessly. Guys, all we need here is a simple equivalent of this code (without any side effect, like 404 header etc).
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
So I continued searching for the perfect solution, and here is what I found. It works like charm on Wordpress 2.5 
Another victory for KISS! (keep it sweet and simple)
Content of /etc/lighttpd/lighttpd.conf
$HTTP["host"] =~ "dev\.sudhaker\.com$" {
server.document-root = "/shared/sites/htdocs_drupal5"
magnet.attract-physical-path-to = ( server.document-root + "/rewrite.lua" )
}
Please make sure mod_magnet is enabled
And content of $WP_ROOT/rewrite.lua
attr = lighty.stat(lighty.env["physical.path"])
if (not attr) then
lighty.env["uri.path"] = "/index.php"
lighty.env["physical.rel-path"] = lighty.env["uri.path"]
lighty.env["physical.path"] = lighty.env["physical.doc-root"] .. lighty.env["physical.rel-path"]
end
A similar workaround for Drupal is suggested here
Note: It only works on lighttpd 1.4.2+ 
Cheers,
Sudhaker