I've seen issues like this before but not to that degree. I don't have document with that many paragraphs but I do have one 982 pages long with over 6,000 paragraphs.
I ran this code in Word 2010 in 2.87 seconds regardless if was on the first page, last page or in the middle. It does have a TOC:
Sub ScratchMacro()
'A basic Word macro coded by Greg Maxey
Dim tm
Dim aParagraph, aStyle
Dim i As Long
tm = Timer
For Each aParagraph In ActiveDocument.Paragraphs
Set aStyle = aParagraph.Style
i = i + 1
Debug.Print "A"
Next aParagraph
MsgBox Timer - tm & " " & i & " paragraphs"
lbl_Exit:
Exit Sub
End Sub