Alan,
Sounds like corruption in one of your message databases. Try to run GWchk32 against the whole post office. Look at the log, and match up the users to what dbase they are attached to. My guess is that what appears to be random is not. GroupWise creates 25 message databases for each post office regardless of the number of users in the post office, and then (somewhat) randomly, distributes them to the message databases. If you find out that all of the users are associated with one or two message dbs (form for the dbs are msg??.db) you can put your attention on them.
When a message has an attachment larger than 4kb (I think that's right) or so, it will take the attachment and put it into the offiles directory with a link back to the message in the db. If the offiles directory gets damaged or deleted, then the link has nowhere to go.
Check on what message dbs are effected, look at the offiles directory. That might get you moving in the right direction.
Good Luck,
Bruce