Как правильнее организовать архитектуру сервиса?
По первому: наиболее секурно все же отдельные виртуальные машины. 
Однако если вопрос только в БД, при условии нормальной архитектуры самого приложения и бд скажем PostgreSQL/Oracle То я бы остановился на схемах. Причем каждый поддомен работает от своего пользователя/схемы с четко разграниченными грантами. 
С управляющей схемой контактируют только системы полностью изолированные от пользователя.
Начальное копирование баз для posgre, скажем: от простого дампа основной схемы/create table like  до create table of type / inherits
По второму пункту: при грамотной реализации ничего тормозить не будет, во всяком случае у меня 250млн сообщений при 2тысячах активных пользователей не тормозили абсолютно.  Тут больше думать нужно над реализаций самих сообщений. Если скажем мы можем удалять свое сообщение из переписки то его копия не нужна, если не можем то табличка вида
 -message_id
 -message_text
 -message_theme (если нужно)
 -parent_id (для иерархии ответов, если нужно), 
 -folder_id (если нужны папочки)
 -author_id
 -author_name
 -recipient_id
 -recipient_name
 -keeper_id
Решает все проблемы. На каждое сообщение создается два экземпляра и соответственно если keeper_id==author_id то это исходящее, если keeper_id==recipient_id - входящее. Имена отправителя/получателя кешируем в соответствующих полях дабы не выполнять на каждый чих лишний джоин а так же дабы не потерять адресата если вам захочется  потереть пользователя из бд (что само по себе плохая идея).  Определяемся нужны ли темы,папки итд и составляем индексы под наши запросы - все: радость и счастье, бабочки летают.
Вопрос очень простой - когда либо данные одного заказчика могут быть использованы у другого? Нет? Тогда чем меньше зависимостей, тем лучше.
Отдельные базы отдельным заказчикам - это и упростит их внутреннюю структуру и решит вопросы с разделением доступа. Что касается балансирования нагрузки - это решается применением виртуальных машин или контейнеров. 
Так у вас и полная изоляция будет, и снимки на ходу, и другие радости.
Инструменты для контроля за экземплярами ВМ, кластеризации и балансировки нагрузки на кластер  - есть, бесплатны, и весьма удобоваримы.
Мой личный пример - Xen - Pacemaker/Heartbeat - OCFS2