Since it happened too often, I decided to start Mutt inside GDB.
Then one day I got the following :

Sorting mailbox...
Program received signal SIGSEGV, Segmentation fault.
0x080b1eae in check_subjects (ctx=0x8102378, init=0) at thread.c:731
731     thread.c: No such file or directory.
        in thread.c
(gdb) bt
#0  0x080b1eae in check_subjects (ctx=0x8102378, init=0) at thread.c:731
#1  0x080b259f in mutt_sort_threads (ctx=0x8102378, init=0) at thread.c:946
#2  0x080af48f in mutt_sort_headers (ctx=0x8102378, init=0) at sort.c:234
#3  0x08063252 in update_index (menu=0x80ef9e8, ctx=0x8102378, check=1,
    oldcount=0, index_hint=0) at curs_main.c:312
#4  0x080638a3 in mutt_index_menu () at curs_main.c:487
#5  0x0807f6e7 in main (argc=1, argv=0xbffff8b4) at main.c:919
#6  0x4013e90c in __libc_start_main () from /lib/libc.so.6

So Mutt crashes on the following line :

    else if (cur->env->real_subj && tmp->message->env->real_subj)

Back to GDB :

(gdb) p cur
$1 = (HEADER *) 0x80ef388
(gdb) p *cur
$2 = {security = 0, mime = 1, flagged = 0, tagged = 0, deleted = 0,
  changed = 0, attach_del = 0, old = 0, read = 0, expired = 0, superseded = 0,
  replied = 0, subject_changed = 0, threaded = 1, display_subject = 0,
  irt_changed = 0, refs_changed = 0, recip_valid = 0, active = 0, trash = 0,
  zhours = 0, zminutes = 0, zoccident = 0, searched = 0, matched = 0,
  collapsed = 0, limited = 0, num_hidden = 0, recipient = 0, pair = 0,
  date_sent = 1074533472, received = 1074553220, offset = 0, lines = 26,
  index = 0, msgno = 0, virtual = 0, score = 0, env = 0x8101d68,
  content = 0x8114898, path = 0x0, tree = 0x0, thread = 0x8113a68, refno = 0,
  data = 0x0, maildir_flags = 0x0}
(gdb) p *cur->env
$3 = {return_path = 0x80ef958, from = 0x80efb68, to = 0x80ef7c0, cc = 0x0,
  bcc = 0x0, sender = 0x0, reply_to = 0x80ef7a8, mail_followup_to = 0x0,
  subject = 0x8113be8 "Get cheapest Vl@GRA on the Planet! - $2.75$ - oiucygjs", real_subj = 0x8113be8 "Get cheapest Vl@GRA on the Planet! - $2.75$ - oiucygjs", message_id = 0x8102260 "<5$su522c$$4728gbi$-n@6lxxp>", supersedes = 0x0,
  date = 0x8113a48 "Mon, 19 Jan 04 17:31:12 GMT", x_label = 0x0,
  references = 0x0, in_reply_to = 0x0, userhdrs = 0x0}
(gdb) p tmp
$4 = (THREAD *) 0x80efab8
(gdb) p *tmp
$5 = {fake_thread = 0, duplicate_thread = 0, sort_children = 0,
  check_subject = 0, visible = 1, deep = 1, subtree_visible = 1,
  next_subtree_visible = 0, parent = 0x0, child = 0x8113a68, next = 0x0,
  prev = 0x0, message = 0x8113cd8, sort_key = 0x8113cd8}
(gdb) p *tmp->message
$6 = {security = 92, mime = 0, flagged = 1, tagged = 0, deleted = 1,
  changed = 0, attach_del = 1, old = 1, read = 1, expired = 1, superseded = 0,
  replied = 0, subject_changed = 1, threaded = 0, display_subject = 0,
  irt_changed = 1, refs_changed = 0, recip_valid = 0, active = 0, trash = 0,
  zhours = 16, zminutes = 28, zoccident = 1, searched = 0, matched = 1,
  collapsed = 0, limited = 1, num_hidden = 0, recipient = 0, pair = 0,
  date_sent = 1074536881, received = 1074542427, offset = 0, lines = 74,
  index = 0, msgno = 0, virtual = 0, score = 0, env = 0x0, content = 0x0,
  path = 0x0, tree = 0x0, thread = 0x80efab8, refno = 0, data = 0x0,
  maildir_flags = 0x0}

So the code expects tmp->message->env to be non-NULL, but it's NULL.