Я думаю, что в принципе концепция, которую ты выбрал - верна.
Т.е. имеем следующие таблицы БД: messages, geo_tags, attachments
Строки в geo_tags и attachments привязаны к строкам в messages, т.е. в таблице attachments у тебя есть столбец message_id, я думаю тут понятно. Хранить "вложенные" сообщения отдельно - это не правильно, их все нужно хранить в одной таблице, а между ними должны быть отношения предок -> потомок, у одного предка может быть сколько угодно потомков. Если ВК позволяет иметь несколько уровней вложенности сообщений (т.е. внутри вложенных могут быть другие вложенные и т.д.), то тут главное не делать рекурсий, нужно применить паттерн хранения таких отношений, например вот удачный паттерн https://www.percona.com/blog/2011/02/14/moving-sub...
Обязательно проставь индексы и составные индексы исходя из логики твоего кода, это ускорит выборку.