Messages could be split if a user account that was included within the message conversation had been deleted.
Not just...
Delete member and do not alter posts. Ownership will be set to Anonymous with an Anonymous name of: USERNAME
but deleted as...
Delete member and delete all posts. If there are any replies to a post by this member, they will be attached to the post's parent. If the user's post is a topic, the entire topic will be deleted.
Correct me if I'm mistaken, but just quickly browsing through the cleanup code within admin/dodeleteuser.php does not account for attaching Private Messages to the root. (near/below line 198)
As a side note, you may also want to run a reindex/rebuild on your tables from within sql. The server /might have/ had a hiccup and could be garbling the PM database. It's not out of the question - but it wouldn't hurt to do it... after making a backup, of course.
EDIT: Have inactive users recently been purged?