I spent a few hours diving. Here are the shiniest pearls I hence doth bequeath thee:
- Lolita was the first anime-styled visual novel, as asked.
- The Portopia Serial Murder Case was the first visual novel, but I argue that its visual style deliberately mimicked US games of the era.
- Taking the question a little differently for extra style points: Dragon Knight was the first VN game with an anime adaptation.
Juicy details follow:
This eroge from developer PSK was published in 1982 or 1983 (sources disagree). It is the oldest game tracked by vndb. The title screen art is distinctly in an anime/manga style:
And so is the gameplay. Here's a screenshot (thanks user Cor 13 at Moby Games):
The game is basically a video-game version of yakyuken; strip rock-paper-scissors, against the computer. Winning reduces the girl's clothing until she's naked, at which point the police arrive and arrest the player character. (Yes, seriously.)
Here's a gameplay video. The video description credits it as the "first anime game", but does not explain the reasons for that title.
The story is pretty thin, and so are the visuals (also literally), but I would argue that there's still a story there and that it's undeniably visual.
If the facts one day surface, and Lolita actually was released later, this game, developed by Yuji Horii in June 1983 for the NEC PC-6001, would be next in line. Though it is historically very important, its visual style may disqualify it for the specific honour of being the first anime-styled VN.
The game involves solving mysteries by interacting with items, characters and the game world, and Retro Gamer (in issue 85) asserts that it “defined the visual novel genre; it was the first from which all subsequent titles followed”. Those are big words.
However, the cover clearly isn't in an anime style (ⓒ Square Enix nowadays, from Wikipedia):
The in-game graphics were so limited it's hard to tell, but based on a gameplay video (thanks YouTube user cokescrew) the style isn't obviously approximating anime either:
Retro Gamer magazine interviewed the game's developer Yuji Horii in issue 35. I found a copy, and sure enough he explains the game's origin story:
I read an article in a PC magazine about a US genre called ‘adventure games’, which allowed players to read stories on their PCs. We still didn't have them in Japan, and I took it upon myself to make one. [...]
That scarcity is perhaps the reason I couldn't find other old Japanese VNs or text-adventures. The quote does clearly point Portopia's intended genre more at text adventure than visual novel though, and suggests its main influence was western games, casting doubt on its eligibility for the specific honour in question.
If we take the question extremely firmly, to mean that there must be a corresponding anime of that visual novel, then based on Wikipedia's list of anime based on video games, the oldest is this 1989 eroge/RPG by developer Elf still in business! with a 1991 hentai OVA adaptation of the same name.
Here's the game's cover art (ⓒ NEC Avenue Ltd. & Elf; thanks vndb):
Greetings from Game Development SE! ♥