Клиент предъявляет очень жёсткое требование: надо чтобы работало всегда.
я бы сказал это стандартное требование, а не жесткое.
самое правильное решение - это один, но надежный хостер. а как выбрать надежного, это другой вопрос. есть сайты посвященные обзорам хостингов - http://hostobzor.ru/main/, например. подобные вопросы часто обсуждаются здесь на форуме, можешь почитать топики. если хочешь свежего мнения, то можешь собрать статистику кто где хостится.
от себя могу сказать, что сейчас пользуюсь (относительно недавно) peterhost.ru - пока только положительные эмоции. от кого перехожу к нему могу сказать лично, дабы не помешали спокойно перехать.
идеального хостинга не бывает, нужно идти компромисы.
если ты хочешь поделить риски между двумя хостерами и тебя интересует чисто технический момент, то я думаю что реализовать мгновенное перенаправление домена на другой хостинг в случае отказа, сделать будет практически невозможно в силу специфики работы DNS-серверов. (в этом я не большой спец, поправьте, если ошибаюсь) За это время хостер скорее всего уже решит проблему.
Да и как ты в этом случае будешь обеспечивать синхронизацию данных на 2-х разных хостингах?