From what I have read you can, but the updates occur slower because a trunk is taken up for the communication. If you don't have a lot of capacity then this would be even more the case. Harry 111, how many trunks do you have between sites? And how many extensions are at the remote site? If there's a disparity then therein might be your problem. Do you see errors in the System Error Log indicating MWL timeout issues?
Looking at my Network Reference manual that Avaya put out E&M tie lines are indeed supported for the MWL feature, but the update traffic competes with other calls along the trunks. And I would imagine any internal contention priorities wouldn't favor the MWL updates.
Since these are presumable prviate point to point lines why don't you consider provisioning them as PRI? Replacing the E&M cards with DS1 cards and using Common Channel Signaling rather than Robbed Bit Signaling will probably give you richer features, improved performance, etc. If it's a private line you can decide what to put on it. Using E&M you are going to run into TTR resource issues (causing calls not to be handed off), lack of ISDN identifiers, slow MWL updates, longer call setup times, etc.