Sometimes, a setback [1] is just what we need to clear our minds and rethink the problem.
Postfix [2] and Sendmail [3] handle external policy checkers differently (and I assume Qmail [4] handles them differently as well).
The solution?
Write the Postfix and Sendmail policy checkers to talk to a long-lived graylist daemon [5], which should simplify things quite a bit.
Now that I've decyphered the Postfix protocol [6] (it's only when you check the example graylist server that you find some critical information not mentioned in the documentation—sheesh) things should go a bit more smoothly.
[4] http://cr.yp.to/qmail.html