While I am not 100% certain, how StraightTalk systems "provision" your VVM settings, I can say that with the carrier I work for, we attach it to the Cellular Data plan. VVM, depending on carrier, requires cellular data to be working, to sync with the network. StraightTalk uses T-Mobile coverage, where I live. T-Mobile uses GSM technology(i.e. SIM cards for any T-Mobile device).
My carrier uses GSM, as well. When iOS 7 first launched, on 7.0, many customers could not get their VVM. This only seemed to affect new iPhone 5s models. The exact symptoms were as follows: the phone would dial the basic VM, when tapping the VVM icon, in your phone menu, despite having correct VVM features in the network. This required us to have the customer do many of the steps,you have done, and continually send Ovet-the-Air signals, to the phone.
Don't ask me why, but iPhones are the ONLY phones that a carriers network has zero capability, to access the phone. As I posted, on another forum page, my Nokia Lumia 820(model RM-824[at&t]) does not have this problem. I also can't setup or change my basic VM, without calling my basic VM. For whatever reason, Apple feels a need to set the carrier settings into the iOS, and that is where the issues lie, hence the "Reset Network Settings". Take your phone to Apple, and they will just send you back to your carrier, and blame it on the carrier. As much as I hate to say this, Jeff, you will probably have to call Straight Talk, again.
Before you do, can you give me a description, of whether you are on cellular data or wi-fi, when accessing the VVM? Also, tell me what happens, when you try to access you VVM, please. Finally, as I know this is a pain, but are you able to retrieve your basic VM, by calling it? Also, who is the provider, that gives you coverage with Straight Talk, in your area?
I may not have all the answers, because I don't have access to StraightTalk technology and systems, but I will do my best to research it and see what I can come up with. I'll do my best to help you folks out.