Welcome to the community!
The actual voicemail messages are stored on in your mailbox on Fido's voicemail servers. When you receive a SMS notification, those are stored on your phone. Deleting the SMS notifications from your phone has no bearing on the messages stored on the servers.
Unless they changed the system recently, pressing 1 does not delete the voicemail messages. If you wish to delete the messages without listening to the entire message, you would press 77. Once the message has completed playing, you can delete the message by pressing 7 (see here under Managing your Messages).
Hope this helps 😀