If it's a landline it could store the voicemail on device, which is how phones used to work (or prior to that, you'd plug an answering machine into the phone). A GB of flash would be basically unlimited and cost a couple cents. You could play an old school "your call could not be completed as dialed" message if it's actually unavailable due to a power/network outage or something.
reply