This is CSCec72292/CSCdu29062, wherein the phone tries to be smart and call from the first line that has an activated message-waiting indicator. Under CallManager 3.3(3)sr3 and above, there is a new Service Parameter you can set to force the phone to always dial out from the first line if you hit the Messages button while on-hook, without regard to which if any lines have MWI turned on. You can access it from CCMAdmin, from the Service menu, Service Parameters, and pick CallManager from the drop-down service list.
Always Use Prime Line for Voice Message: This parameter determines whether the primary line gets chosen and becomes the active line when the Messages button is pressed. Valid values specify True (pressing the Messages button causes the phone to automatically dial the voice-messaging system from the primary line) or False (pressing the Messages button causes the phone to automatically dial the voice-messaging system from a line that has a voice message).
This is a required field.
Default: false.
If you are on a version of CallManager below 3.3(3) and can't upgrade, you are unfortunately out of luck. The workaround is to touch the first line button to go offhook on the first line, and then hit the Messages button.