A base station in a wireless communication network multi-codes a shared packet data channel using a continually changing set of spreading codes, and dynamically updates the transmission frequency of messages identifying the spreading codes to be used for that multi-coding based on tracking the net gain in data throughput for the shared channel that is obtained by transmitting such messages. In a 1xEV-DV network context, for example, a Walsh code in the defined Walsh code space that is not contiguous with the Walsh codes currently allocated to multi-coding the 1xEV-DV Forward Packet Data Channel (F-PDCH) generally remains unavailable for such use until an updated Walsh Mask Broadcast (WMB) message is transmitted to the mobile stations being served on the F-PDCH. The base station thus is configured to determine the frequency at which to send such messages and thereby make the unavailable codes available for multi-coding use.