I have Facebook app as a page tab and sometimes it did not get the signed_request.
I saw with Firebug that POST to my app is made and signed_request is there but this call made redirect to GET instead. This was always reproducible with one Facebook account but with another account it worked just fine. I used Laravel framework and tried adding debugging code to index.php where all requests are routed through and also created separate index.php so that .htaccess would be bypassed. It turned out that POST request is not reaching the code at all.
What I found out is that even though I run all the services over HTTPS and in Facebook app config I have only HTTPS links then Facebook still forces app to be loaded over HTTP. I have apache2 virtual host configuration so that all HTTP requests are redirected to HTTPS which loses all the POST data and that is why the guaranteed signed_request never reached my app.
I resolved it by allowing HTTP but any navigation in the website was changed to HTTPS again.