I have exact this problem:
Sometimes and with some users the page does not load, and shows random errors with
"Fatal error: Maximum execution time of XXXXXXX seconds exceeded in ..."
I'm 90% sure that is something related with the cookie because in private mode loads normally and if I clean my cookies in my browser then loads.
I don't want to disable persistent shopping cart, I don't know if there's a configuration about cookies that I'm missing.
Session Cookie Management Cookie Lifetime: 86400 Cookie Path: Cookie Domain: Use HTTP Only: Yes Cookie Restriction Mode: No