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, but it was still "with 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.