Any suggestions on a server based encoding solution (like YouTube or Vimeo) that I could run on a Linux server?

HI

Check out sorenson media site. They had an offering like youtube at last NAB. I think its called squish.

Chuck