I have MWI working pretty nicely with a set of Polycom 501/320s on Asterisk 1.6.0-beta8 in Realtime mode. The normal SUBSCRIBE/NOTIFY sequence seems broken, Asterisk seems to choose a random number of new messages it will send in the NOTIFY message, so I have a script that will compute this and generate a real NOTIFY packet using sipsak.

It's adapted from a previous script I found at (http://lists.iptel.org/pipermail/serusers/2005-May/019684.html), so much credit goes to the original creator. This can be adapted into an OpenSER setup as well to solve MWI issues.
In my setup this script is called from Asterisk in externnotify to send an MWI as soon as voicemail is left, as well as in a cron job to send out MWIs in the case that the phone was off / not registered when the message was sent.

in sip.conf you need:
[general]
; This seems like a mistake, it's not. We want to disable Asterisk from sending out
; bogus NOTIFY messages. Polycom's will still accept NOTIFY messages
allowsubscribe=no

in voicemail.conf you will need
[general]
externnotify=/path/to/notify-script

By the way, the SIP NOTIFY section must use <CR><LF> for new lines, not just <CR>. I hope this is helpful to someone.