Here is the solution along with how you can debug mod_rewrite problems.
Add these two line to your httpd.conf immediately after RewriteEngine On.
After that I added the required RewriteRule etc.
The reason for testing directly in httpd.conf is to ensure that mod_rewrite is working in the first place. After some debugging I realized my expression was wrong. So now I found mod_rewrite was working in httpd.conf. However it still wasn’t working in .htaccess files.
I found AllowOverride was set to None in httpd.conf. I changed it to All (after all I am the only user of the machine). And it finally started working everywhere (after a restart).