What to do when you can no longer login to your Drupal site

So the scenario is this: you notice that you are no longer able to login on your Drupal site:

• the {users} table entry for your account looks just fine
• the login and access timestamps on your account are just a few seconds old, matching your latest attempt to login
• you reset your password in the DB, just in case, and it still does not work
• the telltale is that Drupal will not even tell you your login failed: it actually works, as the {users} table shows, but yet you are not logged in

Can you guess what can have been going wrong and fix it ?
Actually, in such cases, and at least on most sites without high-end technologies like Memcached or MongoDB sessions, there is one other table you should be looking at, and that is the {sessions} table. If, like most Drupal sites, you are running on MySQL, chances are that your {sessions} table has crashed. This is most common in Drupal versions up to 6, which use the MyISAM engine by default, typically unchanged on smaller sites, whereas Drupal 7 defaults to InnoDB, and larger sites will also have installed Drupal 6 on InnoDB too.
What is happening in such a case is that Drupal actually updates your login entry into the {users} table, but then when the page ends, PHP tries to invoke the Drupal DB-based session handler to write back information about your session into the {sessions} table, and fails because the table is crashed. If you look at your web server logs, you will then notice tons of messages like this (typical Apache: /var/log/apache2/error.log):

[Thu Aug 04 09:34:27 2011] [error] [client (IP masked)] 

PHP Warning:  Table './(site masked)/sessions' is marked as crashed and last 

(automatic?) repair failed\nquery: UPDATE sessions SET uid = 0, cache = 0,

 hostname = '(IP masked)', session = 'language|s:2:\\"en\\";',

 timestamp = 1312443267 WHERE sid = '1c3a573a10ff949d31c193c42365c7d7'

 in /(path masked)/includes/database.mysql.inc on line 174,

 referer: http://(site masked)/user

These happen when Drupal tries to update a session entry. And then tons of similar messages on SELECT queries instead of UPDATE for the attemps by Drupal at locating an existing session for the user.
The solution is then obvious: ssh to your server and run something like:

mysqlcheck -rev (your database) sessions

Do not forget to add the DB prefix if your are using one, like this:

mysqlcheck -rev mysingledb site1_sessions

This should restore your table to sanity. If you do not have access to a command line, as can often happen with smaller sites on shared hostings, phpmyadmin includes an option to "repair" a table, which does essentially the same thing.
One point to notice about this is that it will lock the table during the entire repair process, so your site will be frozen in the meantime.
Afterwards, you might want to consider taking a backup of your site, then converting it to InnoDB. Do not forget that this means a different configuration in /etc/mysql/my.cnf to attain good performance: you will likely want to reduce the memory space allocated to MyISAM and increase the InnoDB buffer pool, for a start ; then follow one of the InnoDB optimization tutorials available everywhere.
Oh, and if you are still running a Drupal 5 site, it is high time to upgrade: Drupal 5 has been out of support for over six months now ! Time to rebuild on Drupal 7 !