Проблема в том, что если возникают какие-то проблемы при принятии ответа от Вашего сервера сервером ВК, то ВК может отправить на сервер несколько запросов, если он не получил удачный ответ от Вашего сервера. И Ваш сервер покорно принимает дублированный запрос и отправляет сообщение. Этот запрос может спокойно прилететь спустя несколько недель. Поэтому необходимо использовать при отправке сообщения параметр, который выделен на приложенном скриншоте.
P.S.: надеюсь, у Вас будет работать (у меня поначалу все работало, а потом что-то как-то не вышло)
