The present invention extends to methods, systems, and computer program products for adaptively selecting electronic message scanning rules. Embodiments of the invention relate to dynamically (and potentially unpredictably) varying the depth/thoroughness of classifying electronic messages to protect against undesirable message content (e.g., SPAM, viruses, digital leakage, etc.). A minimum effectiveness is maintained and, when available resources permit, can be exceeded to provide increased protection. An optimal subset of available message classification rules can be selected on a per message basis. The selection of rules is based on available system resources, minimum desired effectiveness (e.g., defined in a Service Level Agreement (“SLA”)), and rule characteristics. Feedback loops can be used to optimize selected classification rule subsets.