One corrupted document would have been too easy
I'm pretty sure the page numbering and toc numbering uses the same numbering system as the field numbering or automatic list numbering. Also, the problems I refer to were re Word 2002 and maybe 2003. I don't know if MS fixed it in 2007 or 2010.
When you view the actual page number fields, do you see anything unusual? I was going to ask you about your toc, but I realize I don't remember enough of what I learned when I was doing them, and I never did that many. I did do some tweaking using styles. It might be worth checking that all your headers have the same style/styles however you intended.
Sorry if this one is too obvious - are you editing the document on different computers with different printers?
Have you asked about this in one of the microsoft.public.word newsgroups (microsoft.public.word.numbering or microsoft.public.word.formatting.longdocs - there's a proper way to cross-post)? The old newsgroups are still being maintained, just not on microsoft servers. I use nntp.aioe.org. The "official" microsoft newsgroups, where I think most of the MVPSs hang out, still exist with a web interface, try http://social.answer.../category/officeword
I haven't used them since I haven't had a problem sufficient to register and open an account. I think maybe you do.