А что нужно для управления сервером кроме shell и root?
Расстояние - не помеха, зависнет машинка - "reset" нажмет тех. поддержка.
Rackspace - 280 дней uptime RH 6.2 реальный известный мне случай. Они дают в аренду качественно собранные машины, но и береут за это $$$.
RackShack - дешевле, но и канал основной на Cogent - считается не слишком качественным, ругаются на них на разных форумах. Серверы, которые они дают в аренду - получены скупкой на аукционе оборудования компаний-банкротов. Зато дешево
