Keith,
I would take a look in the various messaging server logs and /var/adm/messages. there's a chance you may be exhausting a system resource, ie out of disk/swap space etc.
I have several users with over 20,000 messages and over 2GB of mail. I haven't experienced any reconstruction issues. Platform: Solaris 8 w/Cluster 3.0 4GB RAM.
HTH,
Roger S.
Keith,
There are several caching paramters that you can try adjusting upward. Among them is nsmsgAuthcachesize which is set to 10000 on my systems (production and test). The others are nsmsgLdapmemcachesize and nsmsgDbcachesize.
It's just a (wild) guess that reconstruct is running out of space/memory. Also, there is a msg.conf:local.tmpdir parameter. Maybe that directory is running out of space (or inodes).
HTH,
Roger S.