아바타 채팅 서버를 만들고 있습니다. 보통 온라인 게임에서 캐릭터의 좌표 정보는 어떻게 동기화 시키나요?

요즘에 알바로 아바타 채팅 서버 프로그램 제작을 하고 있습니다.
클라이언트는 플래시 이고 XML Socket을 이용,
서버는 RHEL 5에서 C++ 로 짜고 있습니다.

물론, 저는 플래시는 못하기 때문에 클라이언트 제작하시는 분은 따로 있지요. :)
아무튼 내용은 간단한 아바타 채팅인데, 채팅 자체적인 기능(방 기능 / 귓속말 기능 / 아바타 꾸미기 등등)은 문제없이 구현 했는데..
캐릭터를 방향키를 이용해 좌우로 움직이게 하는 작업이 말썽이네요.

구현은 쓰레드를 이용해서 다중 연결을 구현 했고, 모든 쓰레드들이 유저들의 리스트를 공유하고 있는 형식입니다.
문제가 어디서 생기느냐 하면, 캐릭터들이 좌우로 이동을 하면 그 좌표 값들을 서버가 알고 있어야 하는데..
그 차이가 점점 나게 되어서 나중에는 순간 이동을 하는 캐릭터들이 생기게 되더군요.

키 이벤트가 있을 때 마다 계속 좌표를 보내는 방식은 오버헤드가 커서(데이터가 xml이다 보니..)
키가 down 된 상황에서 서버로 움직임을 시작한다는 메시지와 좌표를 보내고..,
클라이언트에서 해당방향으로 계속 움직이다가..
키가 up 되는 상황이 오면 서버로 움직임을 멈춘다는 메시지와 좌표를 보내면...
그 좌표를 서버가 저장을 해 두고..다시 클라이언트로 보내서 캐릭터를 그 위치에 위치시킵니다.

이렇게 하면 미묘한 차이야 그다지 문제가 없는데.. 간혹 꽤나 큰 차이가 생겨서 순간이동을 하는 경우가 생기네요.
혹시 온라인 게임 같은 것 만들어 보신 분이 계시면 서버와 클라이언트의 좌표 정보를 어떻게 싱크 시키는 지 알려주시면 감사하겠습니다.

ps. 부차적인 질문으로, 위와 같은 구조로 쓰레드를 구성할 경우에 mutex 가 필요한지도 궁금합니다. 일단 유저가 추가 되고 삭제 되는 부분은 mutex로 lock을 걸어줬는데, 좌표 저장 할 때 등등도 mutex로 lock을 해야 하는 지 궁금합니다. 한 두명으로 테스트 할 땐 동기화 문제가 거의 없었는데, 4명 정도만 돼도 눈에 띄게 문제가 생기네요 ㅠㅠ