Looking further, there are a couple circumstances where it won't reproduce:
   • There needs to be newlines after the message call to reproduce
   • eval-last-sexp needs to be invoked through a local keymap

Let ~/emacs-local-key.el contain:
   (local-set-key (kbd "<f5>") 'eval-last-sexp)
Or you can do so in an emacs-lisp-mode-hook.

Steps:
   • Run: ./src/emacs -Q --load ~/emacs-local-key.el
   • C-x 3
   • M-x buffer-menu
   • Select *Messages* (now left window is *Messages* right is *scratch*)
   • C-x o
   • Input: (message "a")
   • Enter a couple times so as there are new lines after the message call
   • Move point to after the close paren above
   • Use f5 to eval-last-sexp, no change in *Messages*
   • C-x o
   • Now all the "a" messages appear

I tried sizing the window to the left and to the right, still can reproduce.

Using emacs -nw I can reproduce it.

I'm on RHEL 5 OS.