Voicemail notification but no voicemail...

bernichani Where's the user's Exchange mailbox located? Teams users with on-premises Exchange mailbox may use voicemail with Teams and receive voicemail messages in Outlook, but voicemail messages will not be available to view or play within the Teams client.
https://docs.microsoft.com/en-us/MicrosoftTeams/exchange-teams-interact

For Exchange online mailboxes in a hybrid scenario when VM's are not delivered to outlook please check below
Voicemail messages are delivered to users' Exchange mailbox via SMTP routed through Exchange Online Protection. To enable successful delivery of these messages, please be sure that Exchange Connectors are configured correctly between your Exchange servers and Exchange Online Protection. Use Connectors to Configure Mail Flow.
https://docs.microsoft.com/en-us/microsoftteams/set-up-phone-system-voicemail