This may be due to corrupted database data.
Have you tried to truncate, analyse and repair both
NOTE: This will empty all guest carts
It is important to always verify both the server and Magento logs
Computer / Browser Related
I'm surprised that clearing Magento cache affected the issue positively, I would usually aim for the browser cache when it comes to session. This can also be a problem related to a specific computer having issues with cookie management. You may try with different computers and browsers.
Core file restoration / Fresh Installation
If this does not resolve the issue I would create a complete backup of the filsystem and copy the files from an original Magento installation over the Magento installation overriding all core files with the originals. This may resolve the issue in the case the problem would be caused by modified core files. On the other side if your actual installation relies on modified core files, these changes would be lost. Pay attention not to overwrite the .htaccess file with the default one. You may also try to install a fresh copy of the same Magento version elsewhere and test it to see if your are experiencing the same behavior.
File System Ownership / Permissions
This type of issue may arise when there is a file ownership issue. As Magento 2 maintenance can be done via command line, some ownership issues may appear if the wrong user or root was used to execute the maintenance script. This is a common problem among Magento 2 developers/store managers.
File permissions can also prevent Magento from reading/writing files in some folders therefore preventing further script execution. It is important to evaluate each folder specifically while maintaining the balance between security and flexibility and to never set the file permission to 777.
You may find useful this official Magento guide regarding the subject.
Server Software / Hardware
If the issue persist, we may think of a php or server misconfiguration, or even a hardware failure.