Hi Rose,
"The dial tone should change as soon as someone has left you a voicemail."
That is my understanding too.
"How often is this happening?"
I would estimate on about one in three occasions.
"When you dial 1571 with a normal dial tone are there new voicemails waiting?"
I wouldn't have any reason to dial 1571 if I didn't have the interrupted dial tone, so I can't say.
Regards