It has taken from about 5ish until now to figure out why my recipient policy was not finding anyone. When specifying group membership in Exchange 2003, you must specify the distinguished name, not just the short group name, as explained in this KB article.