Service Desk will always assume there is a From address on the emails it reads so you're right that these are causing the errors. To be honest I've never seen software generating an email that simply ommits it like that! There isn't anything we can do to change Serivce Desk's requirement so these messages will need to be dealt with before they reach the us.
If there is no way to force the voice mail system to use a default From address in these instances then there may be ways to workaround it in Exchange by setting up some rules to auto-forward the messages somewhere else and bounce back or use some other 3rd party mail tool to do the same. Your mail admins will hopefully have some ideas on what's possible.
I hope that helps.
I know this an old one but did anyone find a way around this problem? We have exactly the same issue, we did have a rule in place for all voicemails but after upgrading to 2016.3 we had some problems with them processing using this method.