Боюсь сглупить, но если бы я писал что-то такое на прикладном уровне, я бы выделил отдельную базу, на толстом канале и выч. мощностях. Думаю, что для каждого юзера отдельная база - это слишком круто. Можно предположить, что разработчики контакта держат несколько баз для этих дел по одной на город России (для примера). Москвичи хранят в одной, Волгоградцы - в другой. И не так накладно и не так загружено. А вообще базы данных для того и создавались, чтобы хранить что-то, много и структурировано. Как на больших мегафорумах например хранят ЛС и столько много сообщений? Позаимствуйте у них

Вспоминается притча:
Большая выставка картин, скульптур и прочей такой высокой шняги. Много охраны, снайперы по крышам, и вообще муха не проскочит и вор не прокрадётся. Ну вот приходит человек и говорит охраннику:

- Я профессиональный вор и завтра я что-то здесь украду. Следите за мной и будьте на чеку!

На следующий день этот охранник только и дело, что следил за этим человеком. Человек ходил, смотрел, но так ничего не украл. После выставки человек сказал охраннику:

- Сегодня я своровал достаточно. Но завтра я унесу ещё больше! Следите за мной и будьте на чеку!

На следующий день история повторилась. И на следующий тоже. И тут охранник не выдержал и спросил у человека после выставки:

- Скажите уважаемый вор, как вы так ловко воруете, а главное, что вы воруете, ведь ни один из экспонатов не пропал!

И человек ответил:

- Я художник... и я ворую идеи...