i may have found our performance issue that some players are experiencing.
From The Wiki Bug List:
Theres a file called map.txt in the achievement folder inside minecraft.jar that causes performance issues. Removing it may greatly increase your performance, but may reset your achievements.
So as I suspected, it is a 1.5 SMP issue and not a mod or server issue.
Also a quick void fix:
Enormous, cuboid areas (usually one or two chunks) of unfinished map open in random places. Caves, minerals, water, magma and mobs are visible when a Player peers into one of these voids. These areas cannot be walked on, causing a "[user] moved wrongly!" message to appear in the Server; however, players can ride minecarts through them with relative ease. If the void appears in the middle of water, Players can "float" over the void using a boat. Placing a torch next to one of these "void holes", dumping lava or water nearby, or disconnecting and reconnecting to the server will make the land inside of them reappear. These have become significantly less common since the 1.3 update.
Some more quoted bugs that might be problems with performance:
Seemingly as of Beta 1.3, some players have been getting huge amounts of strange lag. They get good fps, but everything from placing blocks to damaging mobs can take anywhere from 10 seconds to 6 minutes. It is apparently related to the server, and NOT client-sided. The server recieves the data, but takes a long time to send it back out. It appears to only affect 1-2 people at a time, coming and going randomly. [3]
As of Beta 1.5, this problem seems to be less severe, but still exists.
The minecraft server sends unnecessary many but small network packets. Between packets are often less then 0.00001 seconds. Tests have shown that if those packets get manually buffered that some players will have less lag and less disconnectshttp://getsatisfaction.com/mojang/topics/clients_lose_connection_with_exeption_disconnect_overflow_after_few_seconds_on_the_server
A heavy arrow deathmatch causes severe lag on the server, takes minutes to recover. (picking up the arrows helps)
Check the bugs wiki to see if you notice any problems:
http://www.minecraftwiki.net/wiki/Bugs