mmm no conosco mucho de este juego ni de servidores para juegos, pero aqui
http://www.forosdelweb.com/f92/monta...ia-vps-630469/ hay un usuario del foro que dice tener un VPS para ese juego, tal vez podrias comunicarte con el y cosultarle donde adquiere su VPS.
Una de las cosas que si se es que normalmente se requiere que el servidor este en el mismo pais desde donde se conectan los usuarios del juego para asi evitar ping altos.
de todos modos puedes usar el buscador de este foro e intenta conseguir algo sobre "vps tibia" ya que vi por alli que usuarios de este foro han recomendado algunas compañias de hosting que ofrecen servicios de VPS y dedicado para juegos.
saludos y suerte.