What's interesting is that the clients had low framerates. If the problem was for example something incredibly CPU intensive server side (such as perhaps flowing water or sorting) I don't think the clients would behave the way they did. In that case you would have quite responsive clients but a very laggy environment where everything takes long time to complete.
From this I would rather conclude that it's something related to graphics or world simulation client-side. You mentioned a lot of blocks lying around, and I've read that that can be a source of severe lag (probably also related to that possible lag from crystal chests). So as you moved around and picked up stacks the lag should diminish.
The easiest way to avoid this is to make sure all automatic sorting is handled in such a way that overflows can be handled reliably and preferrably routed to a void pipe or recycling machines.
A tip here is that a diamond pipe next to a chest will deposit all filtered items into that chest as long as there is room, but once it's full the items will continue down the line (into any unfiltered direction that is available from the diamond pipe) without dropping. I use this mechanic in my sorting system (you're welcome to check the second and third underground levels of my base to see it in action if you don't get my explanation).
EVE Online characters:
Daedalus II ex-CEO TOGOA, Daedalus III slave of Daedalus II
Little Molok Asura Engineer
"Each day I don't get an attempt on my life by a robot from the future I see as a personal failure"