Hi all,
I had this problem with a customer's site, ZC 1.5.1 with CEON 4.4.1 (UMM edition, but should be the same with base edition).

Dedicated (cloud) server, I (and the people who manage the server aswell) tried to replicate the issue, but didn't find a pattern, never. So debugging was very hard.

Then I asked Jamie (jsweb.co.uk), that now distributes the module, if he ever had such an issue. He gave me a couple of suggestions and one of these was the right one.

He told me that could be related to apache caching if any enabled.

On that server, initially they tried to enable Varnish, but there were many problems. When I first was told about this issue, I immediately thought it could be related to Varnish not being completely disabled. But the server guys told me it was.

When I forwarded them Jamie's suggestion, they found that mod_mem_cache was enabled. It was turned off and the issue disappeared.

They told me that usually they use Debian, where mod_mem_cache is not enabled by default, but on this server (dunno why) it was used Ubuntu, which has mod_mem_cache enabled by default.

So, as tagged, this is a workaround and not a solution, since of course it requires to disable mod_mem_cache, but if you ever run into this issue, you'll look at this workaround as a 'deus ex machina'.