First of all, i would like to notice that VK Security Team rejected submitted ticket to HackerOne, arguing that this is not a concern (refused to pay via Bug Bounty Program).
Private urls were disclosed using Marketing Spy tool Similarweb.
Query pattern :
https://api.vk.com/method/messages.getHistory.xml?chat_id=
https://api.vk.com/method/messages.getHistory?user_id=
From examples, you can find exactly whom belong text (https://vk.com/id35782579 etc)
Real examples:
https://api.vk.com/method/messages.getHistory.xml?chat_id=53&count=200&access_token=06d49531b4c2f27473220fd370eec7bd8e2c9e2a93e840dadf8c55308f13cb15deb0a08f6ca276d1ed7a3&v=5.37
https://api.vk.com/method/messages.getHistory.xml?v=5.73&user_id=134576366&access_token=58415d017330ea9fe09947941c98e5609cdae8c99c7b62afb51aeca3195b6877c37846c23fd1e0f81a903
https://api.vk.com/method/messages.getHistoryAttachments.xml?v=5.0&peer_id=134576366&media_type=audio&access_token=58415d017330ea9fe09947941c98e5609cdae8c99c7b62afb51aeca3195b6877c37846c23fd1e0f81a903!
https://api.vk.com/method/messages.getHistory.xml?chat_id=51&count=200&access_token=06d49531b4c2f27473220fd370eec7bd8e2c9e2a93e840dadf8c55308f13cb15deb0a08f6ca276d1ed7a3&v=5.37
https://api.vk.com/method/messages.getHistory?user_id=360654755&count=0&v=5.52&access_token=cf764813cf1c8324eea0a0f1b3b5b343ffe29db86737fa4d8da005acd5e4a54c6b3d963ea3e12b4205246
https://api.vk.com/method/messages.getHistory?&user_id=35782579&count=1&access_token=12d5ede00dd9d822ec16c13ea16de88699880db4d0eb3ad6ab7338975e4b9f895b4892b78acaf0e45ce36&v=5.73
Messages contain a lot of private information such as passwords to 3rd websites, attached documents etc.
https://vk.com/doc17073210_437580064?hash=669db960772273f0b2&dl=GE3TANZTGIYTA:1520260512:b8dc57b31236577e17&api=1&no_preview=1
Unfortunately, i can't save examples to https://web.archive.org due to robots.txt block. Example urls will expire soon and i can post more to comments.
I believe, such api calls reserved for special purpose, when Police or other government services provide investigations.