I am not sure if there is anything I can do to figure this out based on this information, but maybe a couple of follow-up questions may turn up something. It is usually easier to figure this out onsite.

Do you know the model of your phone system? If you are not sure, is it very old or very new?
Would you know what type of voicemail system is connected to this system?
Usually the Stratagy line of voicemail systems (most common V.M. on older systems) use the star key to log in, not the pound key. The new IPEdge and Strata Messaging Voicemail systems use the # key. Some old or 3rd party may also use the # key.
Are the users pressing a flashing MSG button or are they dialing the voicemail extension directly?
Older Toshiba systems will connect you to your voicemail box when you press the flashing MSG light, but will always connect to the main greeting when you dial the extension. Newer CIX and IPEdge systems should always connect you to your voicemail box.

I can't see how a call on the lines would have anything to do with the voicemail integration. I think there is something else going. Nothing pops into my head based on the information you have provided. If you have a Toshiba dealer that you use, you may need to have them look at this for you.

David
Tele Express Business Systems