I definitely have no new messages, and no old messages saved. The mailbox is as clear as could be.
I've tried disabling and enabling voicemail completely, but it still tells me I have new messages. It's worst when I turn my phone off (at the cinema for example), I then turn it on later and it pops up "you have new voicemail" so I think oooh, missed a call, must be important. Then I hear "You have no new messages..."
I might have to pop into an Orange store next time I'm in town.