Посоветуйте облачный сервис с поддержкой шифрования.

спроси у Егорыча

Самостоятельно шифровать и заливать к примеру на облако мейла не вариант?

http://www.cloudberrylab.com/ попробуйте.

А что бекапить то планируется? Личные данные или корпоративные? Или Виртуальные машины?