Slow VoiceMail notifications

I have a FreePBX (2.11) system with Asterisk 1.8. I have 40 users with Yealink T26 phones. The system is set as Device and Users. I have a Digium PRI card installed. This is a busy Doctors office. They are experiencing an intermittant problem with the voicemail notifications to the phones. This is a blended network with the phones on the PC network. For instance they will check messages before leaving for the evening, clear them out. Upon getting in the next morning, they will have a new message with a date / time of the previous afternoon. I assume there is a refresh sometime overnight. I am using hints to show message status on the phones. What could be causing this? Network congestion?

Any and all suggestions are much appreciated