In SQL table mdl_question_states the question column normally holds the question number which is defined in mdl_question_* tables. But in case of a random question the question column in mdl_question_states contains a question number which is not the real number of the question, instead the real question number is stored in the answer column.

id attempt question originalquestion seq_number answer timestamp event grade raw_grade penalty
31633 1448 650 0 1 random629-dataset49--36.36 1257676851 3 0 0 1
31694 1448 650 0 2 random629-dataset49-36.36 1257681894 3 1 2 1
31701 1448 650 0 2 random629-dataset49-36.36 1257681894 3 1 2 1

So in this case question number 650 is not valid in a sense that this cannot be found yhe question tables, instead number of the question is 629. Moodle extracts the real question number (629). In file ./question/type/questiontype.php there is function history, which produces "History of responses". In the SQL query

$states = get_records_select('question_states', "attempt = '$state->attempt' AND question = '$question->id' AND event > '0'", 'seq_number ASC');

$question->id is the real question number (aka 629, since formerly Moodle decoded the answer field), but question column contains 650, so there are no matches. Instead of this query I modified the source to

$states = get_records_select('question_states', "attempt = '$state->attempt' AND (question = '$question->id' OR answer LIKE '%random$question->id%') AND event > '0'", 'seq_number ASC');

Introduced OR answer LIKE '%random$question->id%' to the condition. This way the query will find regular questions as well as random questions correctly.

In case of a random question the answer column is not valid for further process because of the "randomxxx-" prefix,so further modification is needed.

foreach ($states as $st) {
$st->responses[''] = $st->answer;
$this->restore_session_and_responses($question, $st);

is modified as

foreach ($states as $st) {
$st->answer=eregi_replace('random.*d','d',$st>answer); // modification
$st->responses[''] = $st->answer;
$this->restore_session_and_responses($question, $st);

to remove the unwanted "randomxxx-" prefix.

These small modifications made "History of responses" work as expected. As I see the table structure, this is universally usable for all type of questions/random questions, no problem can arise.

question = '$question->id' OR question = '$question->randomquestionid'

which is more straightforward and safe, but you definitely need both id and randomquestionid, to have history on random and non-random questions as well.

$st->answer=eregi_replace('random.*d','d',$st>answer); // modification

or something similar is still needed to preformat answer column.

Our Moodle is already modified according to this and it works fine so far.

if (!empty($question->randomquestionid) {
    $qid = $question->randomquestionid;
} else {
    $qid = $question->id;
}

in the PHP code, and use $qid in the SQL, but basically you are right. Do you feel up to creating a patch, or do you want to wait for me to get around to it?