So I've been on the phone with Microsoft for over 5 hours now. Looks like there was some sort of unknown corruption in one of the stores of the affected storage group.
Wasted a lot of time checking to make sure that it wasn't caused by a mail loop or excessive spam.
Fix ended up being to move the 5 users off the mail store onto a temp one, unmount the affected store and see if the problem stopped, delete the database files for the affected store, remount it, again make sure that the problem doesn't reappear and then move the users back.
So it took about an hour to actually fix the problem and the rest of the time was spent waiting for someone from the appropriate team to become available and for troubleshooting to isolate the problem.
About the only thing that the tech could recommend to prevent this from happening again is to regularly perform an offline defrag. Problem is, how often should this be performed? Also, I don't find bringing down a store to perform maintenance on it regularly a particularly satisfactory practice.
Then again, I guess I don't have much choice if I don't want the same thing to happen again...