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