(Disclaimer: I work for a telephone and software-based 2factor provider)
If your telephone-based 2 factor authentication is being thwarted by voice mail hacking, the problem lies in the implementation of the phone call itself, not necessarily the method. Unfortunately, certain solutions are built to be "quick and dirty" and just play an automated message that spits out a temporary password 3 times and hangs up. These make it easy for attackers to scrape them out of voice mail boxes.
Properly designed solutions will actually require call affirmation (for example: the user will be asked to press a randomized DTMF digit before a temporary password is spoken). Certain locations (like North America) can take advantage of features like call-forward detection, which can prevent sensitive information from being delivered if a number is determined to be forwarded.
Ultimately, it may not be a silver bullet, but when it's done right you're left with something much more effective than a minimum effort/lowest possible cost approach.