It turned out that there was a nasty bug in the code which was really hard to reproduce, that sometimes forced the app to make API requests in a loop for 10-30 minutes in a row. Only a small percent of clients had that problem, but it was enough to bump into API limits.
It seems that FB API calculates limits based on the number of users of the app, so even with a rather limited amount of calls we had a rate limiting problem. Another observation is that despite the fact that only a limited number of users were doing a lot of API calls, FB did limiting for all users.
Hope that information will be helpful somehow to resolve similar issues.