Sessions / Cookies not working for user login, registration or shopping cart The Problem

One of our sites has recently broken. Users can't login or register, and the shopping cart isn't working either. 

Drupal does not display any errors. Upon clicking the submit button for the forms, it simply refreshes the page as if nothing had happened.

It's just as if sessions have stopped working altogether, which is a little strange, no?

The rest of the site works perfectly well.

No Drupal updates have been performed and no new modules have been installed.

I've been reassured that this isn't a server problem, but I'm still (really) not sure about that. Since I don't have SSH access to the server, I'd like to be sure beforehand.

I'm just looking for possible causes/fixes, and if anyone has had experience with this before, great. Ultimately I will end up checking out the server, but is there any chance it could be caused by Drupal?

Things I've Tried:

I've checked /sites/default/settings.php for the $base_url and $cookiedomain variables, but they are set properly.

This is not a .htaccess problem, either. Regardless of whether I use clean urls or not (site/user or site/index.php?q=/user) it just doesn't work at all.
This is a very old question, but I stumbled on it while having the same issue.

In my case, the "rewrite" Apache module was turned off. I re-enabled it with:

a2enmod rewrite


I could access /user, but could not login (it would loop back, with no error message). I assumed that since I could access /user, my rewrites and htaccess were OK. I could login with "drush uli", but no form would work. Even weirder: in some pages that had query parameters (GET, ex: foo?test=1), the GET parameters would not be passed to PHP. I was searching all over the place, and the solution was pretty trivial :)