The Cycle ID is stored in the Job Group. When it gets updated the Master sends the updated group to all the agents. If an agent isn't connected at the time, the update gets queued and sent over when the agent reconnects. Any pending updates like this should get sent before any new commands (like new execution commands).
Are the jobs triggered on the Master and then sent to the agents, or are they mirrored so they trigger on the agents? If they're mirrored, then it's possible something is wrong and commands aren't being sent to the agent--so it never got the cycle update, but triggered the job itself. If the jobs are triggered on the master, then it shouldn't be possible for an execution command to get to the agent before the cycle update does.
Check the adTempus.service.log files on the Master and Agent to see if there are any errors being reported. You can also query the AgentCommandQueue table in the database for the master and see if there are any records with an old timestamp that could indicate an update stuck in the queue.
If the queue table is empty and there aren't errors in the logs, try editing and saving the group on the Master. This should cause it to mirror it out to the agents again with the new cycle id.
If you by chance have service debug logs for the master you can open a support case and we can look through them to try to piece together what happened.