По ВК советую рекламровать через оф. биржу ВК, получается намног дешевле, чем напрямую. Только всякий хлам через биржу не пропускают.
В последнее время стал пользоватся сендпульсом, нормально вроде рассылает. Есть все перечисленные функции.
Посмотрите в яндекс вебмастере обратные ссылки, может что-то новое заметите. А там можно попробовать еще ссылок разместить на том же ресурсе, возможно, позитивно повлияет на общий тиц.
Все зависит от качества Вашего сайта. В укрнете различные схемы слива трафика предлагают. Может быть обмен, допустим, если информеры установите. Или если у вас очень уникальные и интересные новости. А так в большенстве случаем платно. Раньше у них было около 50$ в месяц за 500 уников в день гарантировано, сейчас не знаю как дела обстоят.
Недавно также столкнулся с проблемой нагрузки на сервер со стороны бинг бота. Пока что таймаут в роботс помогает, но думаю, полностью отключать поскольку толку от бинга не особо много. Общался со знакомыми, обычно все любо отрубают либо ставят таймаут для бота.
Также точно могу сказать, что еще зависит от того, что внутри сайта. Боты бывает создают такую нагрузку, что сайт просто сразу падает.