Какие характеристики хостинга нужно делать упор при создании callback?

Прямо таки вк коллбек сервера пишешь, обратись в вк, может возьмут тебя на работу, ато у них всего один коллбек...

А по делу, ты даже не указал на каком яп пишешь.
Во всяком случае бери простой вдс, ставь nginx, а далее уже то что тебе нужно (php, nodejs, etc..). В любой момент сможешь добрать ресурсов, если будет не хватать.

Обрабатываю ~5 миллионов запросов в сутки на 2х2.4 и 2гб оперативки, все сессии хранятся в mysql, что отъедает большое кол-во памяти, но остается свободно порядка 700мб.