I don't use my cell on Shabbat, it is turned off but calls still go to my Voicemail. Is this permissible? I don't have the option of turning voicemail off only for Shabbat. It seems it is either set up or not at all.
Your case is almost analogous to the video camera debate, where we find a select few big Rabbis disallowing the use of security cameras over shabbos and not allowing the video captured to be viewed. Two that come to mind are Reb Elyashiv & Reb Dovid Feinstein. However your case is different. In the case of the video camera we are dealing with a shvisas keilim (cessation of possessions' work) issue. And while its true that we rule like Beis Hillel that allows your keilim (items) to do 'work' for you on shabbos, that is only true if the keilim started their work before shabbos, such as the vat where wool was put up to soak or the chandelier that was lit, both before shabbos. A video camera that captures new footage every moment is considered to be doing a new milacha which is why apparently these rabbis prohibited it. It should be noted that the Ben Ish Chai in 1910 disallowed using a timer to turn on an electric light based on this logic.
However your case is different. Your case is the nonjewish keili (item) which recorded the message for you. There is no prohibition against this.
No sources so please CYLOR but:
The voicemail goes to a central server at your provider. When you dial in to retrieve your messages you are not accessing a message store on your phone rather you are dialing into a VM service.
Since this server/service is maintained for both Jewish and Non-Jewish customers it would be permitted to have benefit from it even after Shabbat and there is no need to delete your messages.
There may be a problem with the instruction "Please leave a message". as you are requesting a melachah be performed on your behalf. One formulation I've heard suggested is the change the prompt to "If you leave a message, I'll call you back" or similar wording that does not explicitly request the caller leave a message. (No sources to hand, sorry.)