I wonder if your work items are synchronized .... you mentioned that this problem creeps up every few days. Are the users using different work items? If so, then perhaps the newer work items are using a new process, while the older ones are not.

1. In your eclipse client, open up your project area and go to Process Configuration
2. Navigate to project Configuration -> Configuration data -> work items -> Types and Attributes
3. Select "check workflow usage in repository'

If a message comes up indicating there are work items without the current configuration (or something along those lines), synchronize the work items to make sure they are in line with the current process configuration. Be careful tho - If a workitem is in state A, and state A no longer exists, this work item may be stuck in limbo.