First of all, thanks to all of you for your input. I apologize for not following up here sooner. I did get this issue resolved and wanted to post what I found so that it might help someone else in the future.

Just to clarify a couple of issues, the analog extensions are using cheap single line sets with message waiting lights. They are able to dial other extensions, including the VM extension with no issues.

The problem apparently started when the system was upgraded to v4.98 from v4.70 (all three locations). After reviewing the system programming again, I found that SPNET Digit Send (under DM 3.3.4 Networking Options) was set to MCP Signaling. Changing this setting to MGI Signaling resolved the issue.