They do appear to be stored locally, I tried the "airplane mode" method to check...
It also appears tehy can be DELETED remotely. I called voicemail by the old method and deleted the voicemail messages stored on the AT&T system, but they were still on the iPhone. A little while later, I checked again and they were gone.