Since there are very little inputs, I was able to see with a scope that they are exactly those that I simulated in the timing simulation (so I can guess that we can rule out wrong inputs to the simulation). In addition, the design was suppoused to work at 20MHz, and we reduced the working frequency to about 1MHz, still to have this problem. I guess that the timing simulation might not be simulating correctly what happens in the internal logic (as you suggested).
Is there a way to make a more accurate simulation than the timing simulation in Quartus? If not, is it possible to find the bug by looking at the RTL or something of that sort?