... and does this randomly, both in frontend and backend, sometimes showing the correct pages, and rarely an error message saying, that "table '#__session' is marked as crashed and last (automatic?) repair failed".
That was the first clue, but the usual fix - going into the database (with phpMyAdmin for example) selecting the _session table and using the Repair or Flush/Truncate option does not fixed the problem.
Next thing was to check the Extensions>Manage>Database menu item in the Admin to see if something is wrong there, and indeed, there where couple of errors saying that the session table is not like should be. Usually clicking the Fix button solves the problem, but not this case.
Ooops, the light bulb flashed!
Yes, back to the phpMyAdmin, and let's see, how the #_session table looks like. Bingo. The table was damaged beyond repair, there where no columns in it. Probably was a side effect of a writing failure to the table.
From here the fix is simple. The existing table needed to be deleted (first you might need to actually rename it, depending on the exact level of damage) then re-created using the SQL command found in the install package (replace #_ with your database prefix!):
CREATE TABLE "#__session" (
"session_id" varchar(200) DEFAULT '' NOT NULL,
"client_id" smallint DEFAULT NULL,
"guest" smallint DEFAULT 1,
"time" varchar(14) DEFAULT '',
"data" text,
"userid" bigint DEFAULT 0,
"username" varchar(150) DEFAULT '',
PRIMARY KEY ("session_id")
);
CREATE INDEX "#__session_userid" ON "#__session" ("userid");
