Keep this in mind - it's not a bug!
The defect ID is CSCtc43612.
If you cluster Unity Connection servers (pub and sub) and follow Cisco's recommendations to point inbound voice calls at the sub as first choice you'll see this when a caller leaves a message:
It can take as long as 15 seconds before that message shows up in the called user's mailbox (including MWI on). This is apparently due to a timer of 15 seconds for the pub to poll the sub for new updates.
So... if you are lucky, the timer will be around 13 or 14 seconds old when the message is left and the message gets sync'd quickly.
If you are unlucky and your users are picky enough to mention this, the timer would have just rest -- and it takes about 15 seconds for delivery and MWI. :)
of course this varies for every message sent -- average delivery time works out to about 7.5 seconds on unity connection configured in this way.