After some serious research as to why Page Caching is not working on my VPS (Ubuntu+Nginx+PHP-FPM), I realized that below plugin is causing some problem. The w3tc/pgcache directory always looked empty. Upon close inspection I found that files were getting created and deleted almost immediately. I then went on deactivating the active plugins one after the other and found that Page Caching started working soon after deactivating the below plugin.
I know I should probably be reporting this on the respective plugin's support page but wanted to keep the W3TC author and others aware of this problem. Hopefully there is nothing wrong from w3tc plugin's side.