Du hast keinen Kontext genannt, in dem Du das einsetzen willst. Milter klingt nach Mails, d.h. du hast keinen eigenen Code, in den Du das einbetten kannst?
Wie wär's hiermit? Benötigt die Singleline-Option (inline-Flag s), um über Zeilenumbrüche hinweg zu schauen. Von Performance rede ich lieber nicht, de facto macht das Ding drei Matches.
(?=.*\bRing\b.*)(?=.*\bbinden\b.*).*\bDunkel\b.*
Mein Teststring bei regex101:
Ein Ring, sie zu knechten, sie alle zu finden
ins Dunkel zu treiben und ewig zu binden
Wenn das Ganze in PHP mit deinem eigenen Code läuft, geht es ohne Lookahead und müsste schneller sein. Ich habe noch dazugeschrieben, wie man aus einem Wörter-Array eine Regex baut (das Array darf nur nicht zu groß werden :) ). Etwas ähnliches sollte auch in PERL gehen.
$test = <<<END
Ein Ring, sie zu knechten, sie alle zu finden
ins Dunkel zu treiben und ewig zu binden
END;
$words = [ "Ring", "Dunkel", "binden" ];
$regexp = "/\b(" + implode($words, "|") + ")\b/s";
$matches = preg_match_all($regex, $test);
if ($matches == count($words))
echo "alles ok";
Rolf