I've noticed this too with my Galaxy S4. Up until late October 2013, Voicemail had never used more than a few KB of data. In the month since then, it's sucked down 807 MB of data. No idea why it could possibly be using so much, especially since I don't even use the Voicemail app.
Ideas or solutions would be wonderful.