I started working on line-intersect collision to replace the rect-intersect collision, but that was turning into more of a project then I wanted to get into. I eventually stuck with rect-intersect collision and fixed the original problem with a fixed time step technique that EasilyConfused showed me.
Thanks go to Rotaerk in the gamedev IRC channel for helping me with the new server design, and the rest of the gamedev community for putting up with my questions.
If you are interested in trying out Stick Adventures Online, please visit this site: http://www.ifthensoftware.net/StickAdventuresOnline/