Here is a procedure which I can use to reproduce the newline cache
corruption.

1.  Detach attached files test.mbox, test.in, and test.emacs.  

2.  Put test.emacs in place of your .emacs file.

3.  Run emacs.  I used a compilation from trunk revision 117139.

Because I had to try this many, many times, test.emacs puts testing
commands on keys F3 and F4.  So

3.  Push F3 to run rmail on test.mbox

4.  Push F4 to get new mail from test.in

5.  Push "p" to go to the previous message.  You should get a warning
about cache corruption.

The details of the "new mail" in test.in don't seem to matter much, but
it is very sensitive to precisely what is in the existing message in
test.mbox.  I removed everything that I could to simplify the test case.

I hope this is helpful.

                                        Ken