I found few url-rewrite based solution for enabling CleanURL in Drupal + 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).
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*)$ index.php?q=$1 [L,QSA]
So I continued searching for the perfect solution, and here is what I found. It works like charm on Drupal5 and Drupal6 
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 $DRUPAL_ROOT/rewrite.lua
attr = lighty.stat(lighty.env["physical.path"])
if (not attr) then
lighty.env["uri.query"] = "q=" .. lighty.env["uri.path"]
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 Wordpress is suggested here
Note: It only works on lighttpd 1.4.2+ 
Cheers,
Sudhaker