Apparently, in MySQL 5.0.36, there was a bug that prevented INSERT INTO ... ON DUPLICATE KEY UPDATE ... queries from flushing the query cache for the table they were modifying. According to the MySQL manual:

If a table changes, all cached queries that use the table become invalid and are removed from the cache. This includes queries that use MERGE tables that map to the changed table. A table can be changed by many types of statements, such as INSERT, UPDATE, DELETE, TRUNCATE, ALTER TABLE, DROP TABLE, or DROP DATABASE.

But the evidence speaks for itself:

mysql> insert into sessions values ('fooh', 'blah', now())
  on duplicate key update session_data=values(session_data);
Query OK, 1 row affected (0.00 sec)

mysql> select * from sessions where session_id='fooh';
+------------+--------------+---------------------+
| session_id | session_data | date_modified       |
+------------+--------------+---------------------+
| fooh       | blah         | 2007-07-27 07:41:57 | 
+------------+--------------+---------------------+
1 row in set (0.00 sec)

mysql> insert into sessions values ('fooh', 'blah2', now())
  on duplicate key update session_data=values(session_data);
Query OK, 0 rows affected (0.00 sec)

mysql> select * from sessions where session_id='fooh';
+------------+--------------+---------------------+
| session_id | session_data | date_modified       |
+------------+--------------+---------------------+
| fooh       | blah         | 2007-07-27 07:41:57 | 
+------------+--------------+---------------------+
1 row in set (0.00 sec)

mysql> select sql_no_cache * from sessions where session_id='fooh';
+------------+--------------+---------------------+
| session_id | session_data | date_modified       |
+------------+--------------+---------------------+
| fooh       | blah2        | 2007-07-27 07:41:57 | 
+------------+--------------+---------------------+
1 row in set (0.00 sec)

Now, for us the fix is as simple as adding the SQL_NO_CACHE hint to our queries (or updating our version of MySQL, possibly). And, actually, adding it to the session queries isn’t a bad idea anyways — there’s not really any point in attempting to cache data from a table that gets written to with every page load. This could free up space in the query cache for other data that might have a chance of sticking.

As far as I can tell, this bug was fixed in 5.0.41 (at the latest).