Actually the problem was somewhere in the Cisco equipment, as the service provider has confirmed. Some option in their device to conserve bandwidth by compressing voice data was causing this choppyness. As they've turned this option off now, MoH works perfect.