If you think about it the messages must be stored at their end. I can't see that your phone could be the problem.
I gave up on it when I failed to get an important message. There is supposed to be an interrupted dialling tone, (which didn't happen) when there is a message waiting so if this wasn't the case I didn't normally bother to check what with the hassle of putting in the password etc.
I cancelled it and went and bought a single handset with digital answering machine at Tescos for about £27 and logged it onto my existing digital phone system. Much simpler to use. There's a bright red number which shows you how many messages are stored which flashes when there's a new one.