I know what you mean.
Maybe players only move position when the user specifically re-sorts or filters.
If a player logs off, the spot becomes available.
If the user disconnects otherwise, they turn gray and fade over 10 seconds, after which the spot becomes available.
If you are filtering by status (playing/ready/away), then uninteresting players shift to the right, but do not move vertically.
Or something...
Maybe a full blown second-life interface would best.

I would keep the same avatar as I have here.