Strange things occuring with our voice mailbox

We returned home yesterday to the tone signalling a message awaiting us in the voicemail box.The message was retrieved and subsequently deleted but every time we pick the phone up now we are still being greeted with the intermitent tone signalling a non-existant message

Any ideas as to why the system thinks we have a message and then tells us we don't when we dial in to check

We're in the essex area by the way

Ta guys and gals