I was recently bitten by KB910272 (again). For the unfamiliar, this issue causes Sender ID/SPF records with non-class full subnets to be processed incorrectly and mail from those domains to be rejected. The number of such domains is surprisingly large for this problem to remain unsolved in the normal patch cycle... or so it seems to me right now.

To solve the problem, apply the hotfix from KB910272 or, even better, from one of the superseding updates: KB927478 or KB951639.