Another silly error I had to fix on same server as .htaccess: Option FollowSymLinks not allowed here. After I got rid of that .htaccess error from Apache2 logs,  bunch of following lines started to appear.

[proxy_fcgi:error] [pid 17763:tid 140531061487360] [client xx.xx.xx.xxx:16953] AH01071: Got error 'Primary script unknown\n'

And php files started to give 404 not found errors. So it still seemed like something related to mod_rewite or .htaccess. I checked everything and restarted Apache2 and PHP a couple times. But still nothing changed.

Since I already have a perfectly working php app on the server I compared both Apache2 virtual hosts and they were almost identical. I was clueless at this point. I was well over an hour into this error and was pulling my hair. I decided to take a break and did a system reboot.

That magically fixed it. 

Yes, a simple system reboot fixed it. I still have no idea why a system reboot would fix it and not Apache2 restart. I'm thinking this is related to Virtualmin I was using as  the control panel.