That worked. Thanks to everyone.
The final result... my check_message ACL looks like this:
deny hosts = +rbl_hosts
message = UTF-8 not allowed
log_message = UTF-8 not allowed in subject: $rh_subject
condition = ${if match\
{${lc:$rh_subject:}}\
{\N\=\?utf\-8\?\N}\
{yes}{no}}
accept