Doesn't VVM utilize Apple systems installed on the carrier network? If so, then how could it work with any carrier that is not an official partner? I know that doesn't answer the question about whether it works with prepaid generally, but if the carrier, like ST or PP or TMob, isn't an Apple partner, how could the deliver Apple's iPhone VVM?
In anycase, I've found Google Voice to be a worthwhile replacement for the iPhone VVM. Just as 'visual' as VVM but you can also get SMS alerts, transcribed messages, messages available on PCs, tablets, whatever.
Unlocked iPhone 5, unlocked iPhone 4
Unlimited airtime, Unlimited CAN/US long distance, Unlimited SMS to CAN/US wireless numbers
2500 Call Forwarding minutes to CAN/US numbers
Google Voice for visual voice mail with message transcription, conditional greetings, unlimited messages (vs 35 message cap), remote retrieval from any PC or phone, no auto-purge after 10 days and most importantly no $7-$8 charge.