Когда приходит письмо не существующему пользователю sendmail принимает его, и только потом генерит отлуп.

Это происходит потому, что sendmail не знает, о том какие пользователи есть в базе cyrusа. Список пользователей можно задать ему следующим образом:

F{cyrususers}-o |/usr/local/bin/sasldblistusers user: %[^ ]

Тогда пишем хак к sendmail.cf. В mc добавляем следующие строчки:
MAILER(cyrus)dnldivert(0)
HACK(cyrususers)dnl

А хак выглядит следующим образом:
VERSIONID(`$Id$')
LOCAL_CONFIG
F{cyrususers}-o |/usr/local/bin/sasldblistusers user: %[^ ]
divert(-1)
# Add rule to the end of ruleset 98 ( local hack for ruleset 0 )  
divert(0)
LOCAL_RULE_0
# Deliver mails through cyrus mailer for imap users.
R$={cyrususers} < @ $=w . >$#cyrus $: $1
R$={cyrususers}                         $#cyrus $: $1

В связи с этим несколько вопросов.
1. В какой файл записать этот хак и куда файл поместить?
2. В каком месте должна быть строка  HACK(cyrususers)dnl в mc? Строаки с MAILER должны же быть последними.
3. Кто-нибудь проверял это дело на работоспособность?