How about simply storing a logout timestamp in the database when a user logs out? Whenever a user logs in again the timestamp field is cleared and as long as that timestamp field is empty the session cookie is accepted, otherwise ignored and the user is forced to log in again.
Basically we still get benefits from storing the session data client side (much less db access) and only store minimal data on the server side.