Если профиль уже месяц как удалён, то вроде бы уже можно регистрировать новый аккаунт на тот же номер. Или два месяца должно пройти, точно не помню. Но я недавно так и делал - удалил зимой один аккаунт и весной на тот же номер зарегистрировал другой акк. Правда, когда я и его удалил, следующий аккаунт я уже не смог зарегистрировать даже через 3-4 месяца. В любом случае Вам сначала надо было проконсультироваться у техподдержки. А теперь - только просить знакомых или друзей с аккаунтами в ВК, чтобы они им написали (я не буду - сразу говорю)