The first problem was that the cache files were created, but they were never valid - on each request a new cache file was created. It was a noob(ish) mistake - I had two calls to Zend_Session::startSession() in my code, which made the session ID always to change which made the cache validity test to fail. Removed the second call and all was well. Or so I thought...
I moved the code to staging to run some final tests before pushing it live, but the cache started failing again. This time the cache files weren't even being created! The same code works on my machine, fails on staging. The only difference was that I had turned off the loading of Google Analytics in the development environment. But... that can't be it, right? Wrong. On every request the values of the GA cookies are different. The full page cache has a set of settings which dictates what variables are taken into account when creating an ID for the cache: make_id_with_xxx_varialbes where "xxx" is one of get, post, files, session, cookie and by default all are set to true. Setting make_id_with_cookie_variables to false made the cache to disregard the always changing GA cookies which made the cache start working again.
So, if Zend Framework's full page cache starts failing for you, check the contents and behaviours of all the variables - get, post, files, session, cookie - and play around with the cache settings until it starts working again.