Several factors could affect the receipt of messages to some units. The fact that they could send means that the device is recognized on the wireless network. Not being able to do lookups/certificate searches means that the initial challenge response sent to the device was not acknowledged, hence the reason for pending messages. A look at the MAGT (messaging agent) and Synchronization logs may show some non-response items for affected users. The non-acknowledgement may be attributed to loss of connectivity by the device to wireless the network. The BES server however, maintains a constant, direct TCP/IP connection to the wireless network.
By restarting the dispatcher and router service, the BES server sends a fresh (refreshes) challenge response to the BES Infrastructure (NOC). This causes the refreshing of the challenge responses for each "active" device. Hence a flushing of pending messages for affected users.