Hi Nate,
There are a slew of tests you can execute on the data to see if we can narrow down what is causing the issue. However, as you mentioned, you cannot repro the issue on spot and have to wait until it happens again, which influences testing. The next time it happens, try to make note of any particular editing tools/add-ins you were using for feature creation or manipulation during that particular edit session. If it happens, try to go right back in to an edit session and repro those steps to see if the issue occurs again.
You said closing and reopening ArcMap will get the attribute table back to normal. Does this repopulate the fields AND fix the ordering of the FID field?
Another thought, is this shapefile always being edited on in the same MXD each time? If so, you may try moving it to a new MXD in case the issue lies there.
Matt