The javascript for this functionality works only with less than 201 messages. If you want to have a "real" check/uncheckall function simply change the javascript a bit:
viewmessages.tmpl
change line 20
and 29
code:
for (var j = 0; j <= 200; j++) {
to:
code:
for (var j = 0; j <= $messagesize; j++) {
Also avoids unecessary loops if you habe less than 200 messages.