No matter what you do, in terms of clearing your cookies or using different browsers, it keeps happening. Fortunately the solution is pretty simple and I actually found it on their parent company's forums:
Open whichever php.ini file you've set* your site to look at. Add this line at the bottom:
session.save_path = /tmp/php_sessions;
Save it. This should fix the problem.
* On Vidahost you need to tell it where you want the php.ini file to be. To do this, simply add this line to your .htaccess file in the public_html root:
suPHP_ConfigPath /var/sites/w/yourdomain.com/public_html/php.ini
Or you could put php.ini in a sub-folder, but if you do then just change the path above accordingly.