I've never played with Interaction Message Store, but I believe you should still be able to access your voicemail from the client (you should be able to add a view).
Can you see if that works? (I appreciate it may not be how you want the solution to work, but let's just see if we can get Voicemail to play somehow....!_
I know the prompt with *99 says Unified Messaging and you don't have full UM, but will it allow you to retrieve your voicemails, or do you get an error? There are some security settings you may need to play with.
If I get a chance, I will try to set this up in a Lab to see if I can figure it out. In the meantime, you might want to open a Support Ticket.
I'm sure, between us, we'll get there!