Techniques for optimizing distributed anti-virus (AV) scanning are described. In one implementation, a message is received into a multi-node network that includes a plurality of distributed scanning tools. An acceptable scanning policy threshold is determined that is representative of a plurality of individual scanning policy configurations of the plurality of scanning tools. A determination is made whether the message has previously been scanned to the acceptable scanning policy threshold based on a single valued element. If the message has been previously scanned, the message is allowed to be communicated. Otherwise, the message is scanned at the acceptable scanning policy threshold. If the scanning is successful, then the message is marked as having been scanned, and is allowed to be communicated. If the scanning is unsuccessful, the message is prevented from being communicated.