Install microG4Lineage. This is a ROM that is simply LineageOS with microG already installed for you. It mimics Google Play Services. My experience is that it just works.
Free and Open Source Software
If it's free and open source and it's also software, it can be discussed here. Subcommunity of Technology.
This community's icon was made by Aaron Schneider, under the CC-BY-NC-SA 4.0 license.
I'm hoping to stick with vanilla LineageOS.
What do you mean with "visual" voicemail?
Just an app to listen and manage voicemail you received?
I use the lineage dialer for that. Works with my voicemail.
Yes. I can hold the 1 key down, and it will give me a voice menu to listen to my messages, but I get no notification when there is a new message. I previously had an iPhone, and in that dialer there was a voicemail tab that showed my inbox and you could listen to/delete the messages from there (and I got a notification when there was a new message).
There are some Play Store apps that have this function, but I have yet to find one that works without Google Play Services installed
Like @TheBaldness@beehaw.org said, you'd need Google Play Services to get notifications or use an alternative implementation with microG.
You can also search on F-Droid for apps that either use a persistent notification or support UnifiedPush
Just an update in case anyone is facing similar issues;
I installed MicroG on my vanilla LineageOS ROM using the F-Droid repo on their web page. I tried downloading the 'My Visual Voicemail' app again, and it now partially works, but at least it's usable now. I still get a popup when I open the app that says Google Play Services is required, but I can now at least close the dialog to view, play and delete messages. Before it wouldn't let me close the dialog. Not sure if notifications are working as I havn't got a new voicemail yet, but it's at least usable for my purposes