Заметил тут в ВК
 

Значит так страница была заблокирована, сегодня ее разблокировали, соответсвенно просят ввести старый пароль ввожу

и новый + повторить

Нажимаю "Сменить пароль", а появляется вот такое

"Пароль не может быть изменён на старый, так как он был скомпрометирован."


Пароли совершенно разные, но тот пароль который новый ввожу, он стоял на этом аккаунте когда то

ВК хранит пароли?

Вполне возможно, скорее всего не только их...

Контакт хранит всё.. И сообщения, и фотки, и музыку, и видео, и статусы, и пароли и т.п. Удаляй, не удаляй, это всё остаётся в базе.
Для примера можешь загрузить фотку, сохранить у себя её прямой адрес и удалить фотку. По прямому адресу она будет доступна. То же с аватарками.