I have the same problem on my
n95 using Tmobile USA.
It shows voicemail when there is none.
I will try what you said TMAC01 , but what exactly do you mean by leaving myself a voice mail...If I call myself from a different phone then how it is different than someone else calling me and leaving a message and then I going and deleting that message, which has happened quite a few times.