The actual form key is stored in the sessions directory even when using cookies. It could be that your sessions are expiring quite often, sooner than your users can finish their post. If you have access to your php.ini file you can try upping your session.gc_maxlifetime. If this is quite low it can lead to the problem.
