I finally got that lag problem under control. I'm writing this topic for those interested in more technical information on what happened. This took a while to debug as there happened to be two large sources of slowdowns, so looking for a single solution didn't work.

1- LWC using up too many resources
LWC is our plugin taking take of doors / chests / furnaces protection. The latest main update added a way to protect hoppers as well. Unfortunately, a bug caused it to emit signals whenever an item moved through a hopper, no matter if said hopper was protected or not. Hopper clocks (several of them sending items to one another in a loop) made it all the more apparent. As more people created more hoppers, the worst things got. Switching to the latest development version of the plugin fixed this, as its author improved the mechanism.

2- Minecraft 1.6.4 saving structures
As some of you know, the update to Minecraft 1.6.4 was primarily focused on saving the location of structures in preparation for the move to 1.7. This means that the server creates files to record the position of every "natural" structure: strongholds, fortresses, mineshafts, villages and the like. The problem is, as many of you have noticed, there are a LOT of abandoned mineshafts underground. As the server detects every single one, and we have a large map, it creates a huge data file with lots of records. The server has problems coping with that, making it slow down to a crawl. As there is no reason to actually record the location of mineshafts, I merely deleted the file.

This is a stop-gap measure, as the server continously scans and records the location of those spots. Until I find a better solution, I'll periodically delete the file to keep its size small.